Research On Automated Detection And Diagnosis Of Path Divergences Technique In Concolic Execution

Recently, the rapid development of information technology has made network security issues become increasingly prominent. Security vulnerabilities, security attacks emerged in an endless stream. To ensure the safety and reliability of software systems, companies have invested a lot of manpower and resources to conduct in-depth study of software security. Software testing is important to ensure the safety and reliability of software, yet traditional static testing methods can not meet current requirements for software testing. New automated fuzzing test method, although outstanding, but can not fully test all the aspects of a software.Concolic execution techniques have developed rapidly in recent years, and are considered as the most promising technique in the field of software testing. Researchers have conducted numerous theoretical researches and engineering practices in this area. However, concolic execution techniques still face some difficulties. Such as path explosion problem, complex path constraints, environmental interactions, floating point computations, path divergences and so on. Those problems hampered concolic execution techniques used in the real world software security testing.This thesis conducts a depth research on the path divergences problem. Firstly, the technical framework of concolic execution, the current research status, key technical difficulties and solutions as well as typical concolic execution tools are studied. Then, a concolic testing experiment is conducted on CREST, which tested 21 different Linux open-source software programs. The experimental results help to study the popularity of path divergences, the percentage of misleading test inputs in software testing, and the relationships between program size and occurrence of path divergences. Moreover, this thesis manually analyzed path divergences problems found in the experiment and concluded 10 different divergence patterns. Finally, this thesis studied the root cause of path divergences problem, and proposed a “snapshot-based compute–compare method”, which can automatically detect and diagnose path divergences problems. With the help of the preserved “symbol-memory” snapshot information in concolic execution, this method can precisely reason the inaccurate symbol propagation part in concolic execution. Also, the method can accurately locate the inaccurate symbol propagation instructions or source program codes in test programs after a “symbol memory compute” phase. A prototype tool, DivAnalysis, is implemented on top of CREST, and experiments showed that the method is effective.