Search-driven string constraint solving for vulnerability detection
—Constraint solving is an essential technique for detecting vulnerabilities in programs, since it can reason about input sanitization and validation operations performed on user inputs. However, real-world programs typically contain complex string operations that challenge vulnerability detection. S...
Saved in:
Main Authors: | , , , |
---|---|
Format: | text |
Language: | English |
Published: |
Institutional Knowledge at Singapore Management University
2017
|
Subjects: | |
Online Access: | https://ink.library.smu.edu.sg/sis_research/4777 https://ink.library.smu.edu.sg/context/sis_research/article/5780/viewcontent/AcoSolver_icse2017.pdf |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Singapore Management University |
Language: | English |
id |
sg-smu-ink.sis_research-5780 |
---|---|
record_format |
dspace |
spelling |
sg-smu-ink.sis_research-57802020-01-16T10:22:52Z Search-driven string constraint solving for vulnerability detection THOME, Julian SHAR, Lwin Khin BIANCULLI, Domenico BRIAND, Lionel —Constraint solving is an essential technique for detecting vulnerabilities in programs, since it can reason about input sanitization and validation operations performed on user inputs. However, real-world programs typically contain complex string operations that challenge vulnerability detection. State-ofthe-art string constraint solvers support only a limited set of string operations and fail when they encounter an unsupported one; this leads to limited effectiveness in finding vulnerabilities. In this paper we propose a search-driven constraint solving technique that complements the support for complex string operations provided by any existing string constraint solver. Our technique uses a hybrid constraint solving procedure based on the Ant Colony Optimization meta-heuristic. The idea is to execute it as a fallback mechanism, only when a solver encounters a constraint containing an operation that it does not support. We have implemented the proposed search-driven constraint solving technique in the ACO-Solver tool, which we have evaluated in the context of injection and XSS vulnerability detection for Java Web applications. We have assessed the benefits and costs of combining the proposed technique with two state-ofthe-art constraint solvers (Z3-str2 and CVC4). The experimental results, based on a benchmark with 104 constraints derived from nine realistic Web applications, show that our approach, when combined in a state-of-the-art solver, significantly improves the number of detected vulnerabilities (from 4.7% to 71.9% for Z3- str2, from 85.9% to 100.0% for CVC4), and solves several cases on which the solver fails when used stand-alone (46 more solved cases for Z3-str2, and 11 more for CVC4), while still keeping the execution time affordable in practice. 2017-05-01T07:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/4777 info:doi/10.1109/ICSE.2017.26 https://ink.library.smu.edu.sg/context/sis_research/article/5780/viewcontent/AcoSolver_icse2017.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University vulnerability detection string constraint solving search-based software engineering Software Engineering |
institution |
Singapore Management University |
building |
SMU Libraries |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
SMU Libraries |
collection |
InK@SMU |
language |
English |
topic |
vulnerability detection string constraint solving search-based software engineering Software Engineering |
spellingShingle |
vulnerability detection string constraint solving search-based software engineering Software Engineering THOME, Julian SHAR, Lwin Khin BIANCULLI, Domenico BRIAND, Lionel Search-driven string constraint solving for vulnerability detection |
description |
—Constraint solving is an essential technique for detecting vulnerabilities in programs, since it can reason about input sanitization and validation operations performed on user inputs. However, real-world programs typically contain complex string operations that challenge vulnerability detection. State-ofthe-art string constraint solvers support only a limited set of string operations and fail when they encounter an unsupported one; this leads to limited effectiveness in finding vulnerabilities. In this paper we propose a search-driven constraint solving technique that complements the support for complex string operations provided by any existing string constraint solver. Our technique uses a hybrid constraint solving procedure based on the Ant Colony Optimization meta-heuristic. The idea is to execute it as a fallback mechanism, only when a solver encounters a constraint containing an operation that it does not support. We have implemented the proposed search-driven constraint solving technique in the ACO-Solver tool, which we have evaluated in the context of injection and XSS vulnerability detection for Java Web applications. We have assessed the benefits and costs of combining the proposed technique with two state-ofthe-art constraint solvers (Z3-str2 and CVC4). The experimental results, based on a benchmark with 104 constraints derived from nine realistic Web applications, show that our approach, when combined in a state-of-the-art solver, significantly improves the number of detected vulnerabilities (from 4.7% to 71.9% for Z3- str2, from 85.9% to 100.0% for CVC4), and solves several cases on which the solver fails when used stand-alone (46 more solved cases for Z3-str2, and 11 more for CVC4), while still keeping the execution time affordable in practice. |
format |
text |
author |
THOME, Julian SHAR, Lwin Khin BIANCULLI, Domenico BRIAND, Lionel |
author_facet |
THOME, Julian SHAR, Lwin Khin BIANCULLI, Domenico BRIAND, Lionel |
author_sort |
THOME, Julian |
title |
Search-driven string constraint solving for vulnerability detection |
title_short |
Search-driven string constraint solving for vulnerability detection |
title_full |
Search-driven string constraint solving for vulnerability detection |
title_fullStr |
Search-driven string constraint solving for vulnerability detection |
title_full_unstemmed |
Search-driven string constraint solving for vulnerability detection |
title_sort |
search-driven string constraint solving for vulnerability detection |
publisher |
Institutional Knowledge at Singapore Management University |
publishDate |
2017 |
url |
https://ink.library.smu.edu.sg/sis_research/4777 https://ink.library.smu.edu.sg/context/sis_research/article/5780/viewcontent/AcoSolver_icse2017.pdf |
_version_ |
1770575028041023488 |