TL;DR
This paper introduces FormSolve, a novel system that uses concolic testing to automatically discover valid input sequences for web forms. By analyzing client-side JavaScript code and solving constraints, FormSolve can effectively fill complex forms, even those with intricate validation rules, paving the way for more robust web data extraction.
What Problem Does This Paper Address?
The "deep web" contains a vast amount of valuable data accessible only through web forms. Automating the process of filling these forms to extract this data is challenging due to complex user interfaces, interactive elements, and client-side JavaScript validation rules that enforce constraints on both input values and the order of actions. Existing methods often struggle with these complexities, especially when domain knowledge is unavailable. This paper addresses the need for a robust, automated approach to navigate and successfully submit these complex web forms.
Methods
The core of FormSolve is an adaptation of concolic testing for web form exploration. Concolic testing combines concrete execution (running the code with actual inputs) and symbolic execution (tracking how inputs affect program logic through symbolic values and constraints).
Key aspects of their approach include:
- Browser Engine Integration: FormSolve is built on top of WebKit, a browser engine, providing fine-grained control over the browser for faithful emulation of user actions and deterministic behavior.
- Symbolic Tracing at Bytecode Level: Instead of analyzing JavaScript source code, FormSolve instruments the WebKit JavaScript interpreter at the bytecode level. This simplifies constraint generation and handles obfuscated or minified code more effectively.
- DOM Instrumentation: The system instruments the Document Object Model (DOM) API to capture symbolic values from form elements (e.g., text field values, checkbox states).
- Constraint Solving for Input Generation: After executing a sequence of actions, FormSolve uses a constraint solver (CVC4) to generate new input values and action orderings that explore new code paths or satisfy previously unmet constraints.
- Handling Action Order and Values: FormSolve explicitly models the problem of finding both valid input values for form fields and the correct order in which to perform actions, which is crucial for forms with sequential validation.
- User-Realizable Value Constraints: To ensure generated inputs are practical, FormSolve incorporates DOM facts (e.g., available options in a dropdown) as constraints to guide the solver towards user-like inputs.
Datasets
- Synthetic Programs: 1000 randomly generated standalone JavaScript programs were used to compare FormSolve's symbolic tracing with Jalangi.
- Synthetic Web Forms: A suite of 1000 randomly generated web forms, each supplemented with generated JavaScript validation code, was used to evaluate FormSolve against Crawljax and Artemis.
- JSFiddle Examples: 18 real-world form validation examples extracted from JSFiddle were used for evaluation.
- Real Airline Websites: 4 real airline websites with complex validation rules were used for experimental evaluation.
Key Insights and Ideas
- Bytecode-level analysis is a viable alternative to source-level analysis: By working at the bytecode level, FormSolve can handle complex, potentially obfuscated JavaScript more effectively than tools relying on source code instrumentation.
- Concolic testing can be effectively adapted for interactive web forms: The core challenge is moving from analyzing single functions to exploring sequences of user events and their impact on form submission.
- Action ordering is as critical as input values: Many web forms have validation rules that depend on the sequence of user interactions, not just the final values. FormSolve's ability to discover both is a key differentiator.
- Guiding the solver towards "user-realizable" values is crucial: Simply generating any valid input isn't enough; inputs that a human user could actually provide are more likely to lead to meaningful form submissions and data extraction.
- Constraint solving is powerful for complex validation: The ability to encode and solve constraints derived from JavaScript code allows for the discovery of valid submissions even when validation logic is intricate.
Key Results
- Improved Path Coverage: FormSolve explored significantly more distinct paths and achieved higher line coverage compared to Jalangi on synthetic programs.
- Higher Submission Success Rate: On synthetic web forms, FormSolve achieved a higher percentage of successful form submissions compared to Crawljax and Artemis.
- Handling Complex Constraints: FormSolve demonstrated the ability to deal with complex constraints, including string manipulations and integer arithmetic, which were challenging for other methods.
- Advantage of Dynamic Re-ordering: The dynamic re-ordering of actions (Algorithm 2) significantly improved the success rate of finding submissions on synthetic forms compared to a fixed ordering.
- Real-world Validation: FormSolve successfully handled complex validation rules on real airline websites, demonstrating its practical applicability, though with some limitations due to prototype maturity.
Limitations and Future Work
- Completeness Assumptions: The theoretical completeness of Algorithm 2 relies on strong assumptions about the solver and the simplicity of code structure (e.g., limited inter-action communication). Real-world code often violates these, leading to a loss of completeness guarantees.
- Prototype Maturity: The current implementation is a prototype, and further engineering is needed for a full-featured, state-of-the-art browser integration.
- JavaScript Level Tracing: The authors suggest exploring symbolic tracing at the JavaScript source level as a future direction, potentially offering different trade-offs.
- More Robust Dynamic Re-ordering: The dynamic re-ordering mode needs further development to improve its robustness and ability to restrict to user-realizable values.
- Broader Browser Support: Extending the approach to work with more modern browser codebases is a necessary step for wider applicability.
Summary updated