TY - GEN
T1 - Structural Test Input Generation for 3-Address Code Coverage Using Path-Merged Symbolic Execution
AU - Hussein, Soha
AU - McCamant, Stephen
AU - Sherman, Elena
AU - Sharma, Vaibhav
AU - Whalen, Mike
N1 - Publisher Copyright:
© 2023 IEEE.
PY - 2023
Y1 - 2023
N2 - Test input generation is one of the key applications of symbolic execution (SE). However, being a path-sensitive technique, SE often faces path explosion even when creating a branch-adequate test suite. Path-merging symbolic execution (PM-SE) alleviates the path explosion problem by summarizing regions of code into disjunctive constraints, thus traversing at once a set of paths with the same prefixes. Previous work has shown that PM-SE can reduce run-time up to 38%, though these improvements can be impaired if the summarized code results in complex constraints or introduces additional symbols that increase the number of branching points in the later execution.Considering these trade-offs, examining the ability of PM-SE to generate branch-adequate test inputs is an open research problem. This paper investigates it by developing a technique that extracts structural coverage-related queries from disjoint constraints. Using this approach, we extend PM-SE to generate branch-adequate test inputs.Experiments compare the effectiveness and efficiency of test input generation by SE and PM-SE techniques. Results show that those techniques are complementary. For some programs, PM-SE yields faster coverage, with fewer generated tests, while for others, SE performs better. In addition, each technique covers branches that the other fails to discover.
AB - Test input generation is one of the key applications of symbolic execution (SE). However, being a path-sensitive technique, SE often faces path explosion even when creating a branch-adequate test suite. Path-merging symbolic execution (PM-SE) alleviates the path explosion problem by summarizing regions of code into disjunctive constraints, thus traversing at once a set of paths with the same prefixes. Previous work has shown that PM-SE can reduce run-time up to 38%, though these improvements can be impaired if the summarized code results in complex constraints or introduces additional symbols that increase the number of branching points in the later execution.Considering these trade-offs, examining the ability of PM-SE to generate branch-adequate test inputs is an open research problem. This paper investigates it by developing a technique that extracts structural coverage-related queries from disjoint constraints. Using this approach, we extend PM-SE to generate branch-adequate test inputs.Experiments compare the effectiveness and efficiency of test input generation by SE and PM-SE techniques. Results show that those techniques are complementary. For some programs, PM-SE yields faster coverage, with fewer generated tests, while for others, SE performs better. In addition, each technique covers branches that the other fails to discover.
KW - Path merging
KW - Symbolic Execution
KW - program analysis
KW - test case generation
KW - test input generation
KW - veritesting
UR - http://www.scopus.com/inward/record.url?scp=85165982360&partnerID=8YFLogxK
U2 - 10.1109/AST58925.2023.00012
DO - 10.1109/AST58925.2023.00012
M3 - Conference contribution
AN - SCOPUS:85165982360
T3 - Proceedings - 2023 IEEE/ACM International Conference on Automation of Software Test, AST 2023
SP - 79
EP - 89
BT - Proceedings - 2023 IEEE/ACM International Conference on Automation of Software Test, AST 2023
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 4th IEEE/ACM International Conference on Automation of Software Test, AST 2023
Y2 - 15 May 2023 through 16 May 2023
ER -