Vulnerability driven hybrid test system for application programs

According to one embodiment, a system receives an intermediate result generated by a compiler based on source code, where the intermediate result includes one or more vulnerability indicators indicating one or more lines of the source code being potentially vulnerable. The system performs a grey box fuzzing on a first executable code generated from the intermediate result to generate a first set of seed inputs. The system calculates a vulnerability score for each of the seed inputs of the first set based on the vulnerability indicators for the lines of the source code reachable but has not been explored by the grey box fuzzing. The system selects one of the seed inputs in the first set having a highest vulnerability score. The system performs a concolic execution using the selected seed input as priority, the concolic execution being performed on a second executable code generated from the intermediate result.

TECHNICAL FIELD

Embodiments of the invention relate generally to secure multiparty computing. More particularly, embodiments of the invention relate to a vulnerability driven test system for application programs.

BACKGROUND

Hybrid fuzz testing leverages both fuzz testing (or fuzzing) and concolic execution to improve code coverage over either one of the approaches alone, however, the code coverage-centric design is inefficient in vulnerability detection as it may blindly explore a code space which may not contain any vulnerabilities. In addition, the coverage-centric hybrid testing quickly moves on after reaching a chunk of code, rather than examining for hidden defects within a chunk of code. Frequently, the coverage-centric hybrid fuzz testing may miss exploitable vulnerabilities despite the fact that it has already explored code paths surrounding the vulnerabilities.

Current coverage-centric hybrid testing methods include Driller: augmenting fuzzing through selective symbolic execution, QSYM: A practical concolic execution engine tailored for hybrid fuzzing; and probabilistic path prioritization for hybrid fuzzing. These coverage-centric hybrid fuzzing methods all suffer from the problems mentioned above.

DETAILED DESCRIPTION

Embodiments of the disclosure disclose methods and systems to evaluating vulnerabilities of a program code. According to one embodiment, a system receives an intermediate result generated by a compiler based on source code, where the intermediate result includes one or more vulnerability indicators indicating one or more lines of the source code being potentially vulnerable. The system performs a grey-box fuzzing process on a first executable code generated from the intermediate result to generate a first set of seed inputs. The system calculates a vulnerability score for each of the seed inputs of the first set based on the number of vulnerability indicators for the source code regions reachable but has not been explored by the grey box fuzzing process. The system selects one of the seed inputs in the first set having a highest vulnerability score. The system performs a concolic execution using the selected seed input as priority, where the concolic execution is being performed on a second executable code generated from the intermediate result.

FIG. 1is a block diagram illustrating a data processing system according to one embodiment. Referring toFIG. 1, data processing system (e.g., host)100may be any kind of computing system, including a server or a cluster of servers, such as Web or cloud servers, application servers, backend servers, or a combination thereof. In another embodiments, system100may be any type of devices such as a personal computer (e.g., desktops, laptops, and tablets), a “thin” client, a personal digital assistant (PDA), a Web enabled appliance, a Smartwatch, or a mobile phone (e.g., Smartphone), etc. System100can include an interface to allow a client to access resources or services provided by system100. Examples of services can include bug/vulnerability analysis, fuzz testing, colic execution, and prioritized hybrid fuzz testing services for software program application source codes. The services can be performed using vulnerability-driven prioritization module110. System100may be configured as a part of software-as-a-service (SaaS) or platform-as-a-service (PaaS) system over the cloud, which may be a private cloud, public cloud, or a hybrid cloud. The interface may include a Web interface, an application programming interface (API), and/or a command line interface (CLI).

Vulnerability-driven prioritization module110can include vulnerability/sanitizer module101, basic block (BB) mapping module105, control flow graph module103, coordinator module107, fuzzing module109, and concolic execution module111. Vulnerability/sanitizer module101can be a tool that identifies potential vulnerabilities within a source code of a software program. These vulnerabilities can include memory corruption, data mismatch, thread related bugs/vulnerabilities, etc. In one embodiment, module101performs vulnerability labeling through a compiler's frontend or backend, such as Undefined Behavior Sanitizer for compiler Clang. In another embodiment, module101is a standalone analyzer that can analyze code regions that contain the potential vulnerabilities and identify the number of vulnerability labels. In another embodiment, the source code can be transformed into intermediate representation (IR) as an intermediate result for code analysis.

Control flow graph (CFG) module103can identify and map a graph of different paths or control flows from one basic block (BB) to another for a software program. Here a basic block or BB refers to a unit of code that contains one or more lines of code or blocks of code within a software program. The graph mapping can be a tree graph, stored as one or more tuples describing one or more branches connecting the BBs together. For a given software application program, module103builds one or more intraprocedural CFGs for each of functions/procedures within the software program and then module103bridges the intraprocedural (or function-level) CFGs by the caller-callee relations to the functions to build an inter-procedural CFG for the software program. To resolve indirect calls to a function (such as through pointers), module103can perform Andersen's point-to analysis on pointers within the application program and to expand functions of any calls if the pointers point to function calls. Andersen's points-to analysis is a static code analysis that analyzes which pointers, or heap references, point to which variables. Pointers analysis can include analysis for four instruction types, for example, addressing of a variable, dereferencing of a pointer, copying of a pointer from one variable to another, and assigning through a pointer. In another embodiment, module103can also apply Andersen's point-to analysis to code with dynamic memory allocation, e.g., code associated with malloc or new memory operations.

Basic block (BB) mapping module105can map each BB within a software program to a number of potential vulnerabilities associated to the BB. The mapping can be stored as one or more tuples for BBs and their associated count of potential vulnerabilities reachable by the BBs. Coordinator module107can coordinate one or more grey box fuzzing and/or concolic executions. Fuzzing module109can perform a fuzzing (e.g., black box, grey box, or white box fuzzing) for a software application program to generate one or more seed inputs. Concolic execution module110can perform a concolic execution for a software application program based on one or more seed inputs. Note, grey box fuzzing refers to a coverage guided fuzzing, thus, grey box fuzzing can prioritize randomized generation of seed inputs that explore new control paths of an application program. Examples of randomized generations include mutations for seed inputs, such as swap bytes, reverse bits of the seed inputs, etc. Note, vulnerabilities reachable by a BB refer to potential vulnerabilities/bugs within a control flow of the BB.

In one embodiment, vulnerability-driven prioritization module110may receive an application program source code from a client for analysis. The source code may be stored in memory150as part of source code151. Intermediate representations (IR) (e.g., intermediate results) of the source code can be generated by a compiler (as part of IR codes153). CFG module103and BB mapping module105then analyze the IR to generate BB mappings and CFGs from the IR code and store them as part of CFG/BB maps155for vulnerabilities analysis.

FIG. 2is a block diagram illustrating an example of a flow chart for a vulnerability driven hybrid fuzz test method according to one embodiment. Flow chart200illustrates the operations for a prioritized hybrid fuzzing with concolic executions for software program(s). Flow chart200may be performed by processing logic which may include software, hardware, or a combination thereof. In one embodiment, flow chart is performed by system100ofFIG. 1. Referring toFIG. 2, processing logic receives target program(s)201. Target program(s)201can be source codes in any programmable languages (C, C++, java, python, objective-C, JavaScript, etc.). At operation1, a compiler with a sanitizer module generates an intermediate representation (e.g., IR code) with sanitizer labels203from the source code of the target programs. The sanitizer module generates one or more sanitizer labels corresponding to one or more compiler injected sanitizer codes representing one or more potential vulnerabilities (e.g., sanitizer/vulnerability labels) in the source code. Note an intermediate representation (IR) refers to a data structure or code used internally by a compiler or virtual machine to represent source code.

Referring toFIG. 2, once the IR code203is generated, at operation2, a static analysis is performed for the IR code203to count the number of vulnerability labels within each BB in IR code203. Processing logic can further label each BB with a BB identifier (ID) and generate a mapping for the BB ID to the number of vulnerability labels within (or reachable by) the BB. Note that a BB refers to a source line sequence with no branches-in except to the entry and no branches-out except at the exit. The basic blocks can form vertices or nodes in a control flow graph (CFG). A CFG refers to a representation, using graph notation, of all paths that might be traversed through an application program during its execution.

Referring toFIG. 2, at operation3, IR203can be compiled into two executables209-211, a first executable209to be used for grey box fuzzing, and a second executable211to be used for concolic execution. Here, only two executables are illustrated, however, more than two executables can be generated so that multiple fuzzing and/or concolic executions can be executed concurrently. In one embodiment, BB pairing information207can be generated. The BB pairing information207can represent a CFG of a target program for priority analysis. The BB pairing information can include one or more mapping tuples, mapping BBs to their edges (or branches) by IDs in a parent-child relationship. Edges correspond to branches of child BBs of the BB being mapped.

Referring toFIG. 2, in one embodiment, a fuzzing iteration is performed on a first compiled executable to generate a first set of seed inputs. Fuzzing or fuzz testing refers to an automated software application program testing technique that generates invalid, unexpected, or random data as seed inputs to a computer program. In one embodiment, fuzzing can monitor for thrown exceptions (e.g., catch/try) for the program. A fuzzer can be a black box, grey box, or white box fuzzer. A black box fuzzer treats an application program as a black box and the fuzzer is unaware of an internal structure of the program. A white box fuzzer has access to an internal structure of the program and can systematically explore different paths in the program based on the access, however, at a high cost of execution time because it takes a long time for analysis. Grey box fuzzers can utilize instrumentation to gather information about a structure of the program. For example, a grey box fuzzer can utilize a tracer to trace basic block transitions/branching for a seed input, thus, can indicate whether there are new branches in the source code being explored. Note that instrumentation refers to the ability to monitor or measure a level of performance, diagnose errors, and/or access trace information of an application program.

In one embodiment, fuzzing generates the seed inputs randomly. In another embodiment, fuzzing generates the seed inputs mutating existing seed inputs. A user configuration for fuzzing may select whether to generate seed inputs randomly or to modify existing seed inputs to generate additional seed inputs.

Once an iteration of the fuzzing completes and the first set of seed inputs are generated, at operation4, a coordinator calculates a vulnerability score for each of the seed inputs of the first set. The vulnerability score can be a count of vulnerability labels of branches that is reachable but has not been explored by the fuzzer for the seed inputs. In one embodiment, the vulnerability scores for the seed inputs are sorted in order and the seed input with a higher vulnerability score is prioritized as an input to a concolic execution. Here, a concolic execution can be executed by a second compiled executable. In another embodiment, more than one concolic execution can be executed concurrently. Note that concolic execution or concolic testing refers to testing by symbolic execution through instrumentation, a technique that treats program variables as symbolic variables, along a particular execution path. Note here concolic execution can be executed for the reachable but unexplored paths for the first set of seed inputs. Based on the one or more concolic executions, a second set of seed inputs can be determined in a vulnerability driven (or prioritized) manner. Here, a priority is given to seed inputs that have a high count of unexplored potentially vulnerabilities within their reach.

Referring toFIG. 2, at operation5, the second set of seed inputs are merged with the first set of seed inputs and coordinator coordinates fuzzing to be performed in a second iteration to generate a third set of seed inputs (which are unique from the first and the second sets). The output is then provided as inputs to one or more concolic executions to generate a fourth set of seed inputs. The iterations can be repeated until a predetermined time has elapsed or until the iterations reaches a vulnerabilities percentage and/or count. In one embodiment, coordinator keeps track of all the seed inputs. In another embodiment, coordinator discards seed inputs which do not uncover new vulnerabilities and/or branches and only keeps seed inputs which explores unique branches and/or vulnerabilities.

FIG. 3is a block diagram illustrating a compiler injected code for a potential vulnerability according to one embodiment. Referring toFIG. 3, a c++ source code301is shown that prints an output for the operations of c=a+b. A compiler with a sanitizer can generate IR code303for the line of code “int c=a+b;” for source code303. Here, IR code303is a handler to catch an integer overflow error, e.g., a potential vulnerability, for code “int c=a+b”. An integer overflow error can occur when the result of an arithmetic operation is not representable in the range of the result type. This can occur when a result of the operation a+b goes beyond [INT_MIN, INT_MAX].

FIG. 4illustrates an example of a control flow graph (CFG) and corresponding mapping tuples for an application program according to one embodiment. Referring toFIG. 4, CFG400can include three basic blocks with IDs: ID(A1), ID(B1), and ID(B2), and two branches with IDs: ID(A1→B1) for branch A1to B1, and ID(A1→B2) for branch A1to B2. Based on CFG400, the pairing information or mapping tuples can be generated to be: {<ID(A1):ID(A1→B1)>, <ID(A1): ID(A1→B2)>}.

FIG. 5is an example of a basic block with reachable vulnerabilities according to one embodiment. Referring toFIG. 5, CFG500illustrates a number of vulnerability labels that can be forwardly reached by a BB. Here, undefined behavior sanitizer (UBSan) for Clang is used to generate the IR potential vulnerability code blocks. Referring toFIG. 5, BB501includes eight child BBs, of which, three BBs contain UBSan (or potential vulnerabilities), e.g., BBs502-504. Thus, BB501has a count of three for the number of potential vulnerabilities reachable by BB501. The BB mapping from BB501to the vulnerability labeling number can then be: <ID(BB):number>, e.g., <501:3>. The BB mapping can be used by a coordinator module to prioritize concolic executions for seed inputs corresponding to the BB.

FIG. 6is an example of a vulnerability score computation for a scenario according to one embodiment. The computation ofFIG. 6can be performed by a coordinator module, such as coordinator module107ofFIG. 1. Referring toFIG. 6, in one embodiment, a coordinator may have initiated a first iteration of vulnerability driven hybrid grey box fuzzing and concolic execution. In this scenario, the fuzzing iteration may have been performed by an executable of an application program having CFG600and may have generated seed inputs601-602. Here, seed inputs601-602can correspond to paths reaching BB D1and BB C5, respectively. The seed input generation may have been randomized or mutated by switching bytes or flipping bits. Next, a vulnerability score is calculated for each of seed inputs601and602to prioritize the seed with higher score for a concolic execution to maximize vulnerability/bug coverage.

Referring toFIG. 6, CFG600can represent a control flow graph (as previously described) for an application program. More specifically, CFG600includes one or more BBs in a tree hierarchy, where each BB indicates a number of vulnerabilities or bugs reachable by each BB. For example, BB A1(denoted by A1:24) can indicate a main node A1has 24 reachable potential vulnerabilities.

In one embodiment, a vulnerability score computation is calculated based on the number of reachable but unexplored BBs corresponding to the BB of the seed input. For example, seed input or path601corresponds to a path from A1to D1. Here, the explored BBs of path601include A1, B1, C1, and D1. The unexplored BBs to path601include D2, C2, C3, and C4. Based on the unexplored BBs, in one embodiment, the vulnerability score can be calculated by averaging a total number of reachable but unexplored potential bugs over a count of the number of reachable but unexplored BBs, e.g., score of path601=¼(4+5+3+4)=4. In another embodiment, the vulnerability score can be calculated based on a solving attempts counter for a weighted averaging.

For seed input or path602, which corresponds to a path from A1to C5, the explored BBs for path602include A1, B2, and C5. The unexplored BBs for path602include C6. Based on the unexplored BBs, the vulnerability score can be calculated by averaging a total number of reachable but unexplored potential bugs over a count of the number of reachable but unexplored BBs, e.g., score for path602=3, the reachable vulnerabilities/bugs for BB C6. Based on the calculated vulnerability scores of paths601-602, coordinator is to select a seed input with a highest vulnerability score, e.g., path601with a score of 4, as the seed input for a concolic execution. Here, the concolic execution is to receive seed input601as a seed input. Concolic execution then replays seed input601and performs concolic execution to explore branch conditions to determine the seed inputs for the immediate reachable but unexplored BBs of path601, e.g., concolic execution determines the seed inputs that can reach BBs: D2, C2, C3, and C4. After a concolic execution for path601is performed, coordinator is to determine the next seed input with the highest vulnerability score, e.g., seed input602. Concolic execution is then to be performed using seed input602since seed input602has the next highest vulnerability score, a score of 3. Concolic execution is then performed to determine the seed inputs for any immediate reachable but unexplored paths corresponding to path602, e.g., concolic execution determines the seed input that can reach BB C6. After concolic execution is performed for the available fuzzing seed inputs, in one embodiment, the concolic execution generated seed inputs are fed back to a fuzzer for a rerun. The fuzzer can then either retain or discard the seed inputs depending on whether each of the seed inputs improves bug coverage. In another embodiment, a solving attempts counter can be increased for branches which are uncovered. As such, a branch having a much higher solving attempt value will be de-prioritized since it has been explored. In one embodiment, a coordinator monitors the generated seed inputs, and initiates another iteration of fuzzing and prioritized concolic execution. In another embodiment, the fuzzing and prioritized concolic executions can be iterated until a predetermined time or iterations have occurred. In another embodiment, the fuzzing and prioritized concolic executions can be iterated until a predetermined percentage of bug coverage is achieved.

Note that the vulnerability scores is used to prioritize seed inputs that can lead to more unverified bugs, while in the long run it should not be trapped in any hard-to-solve branch conditions.

FIG. 7is a flow diagram illustrating a method according to one embodiment. Process700may be performed by processing logic which may include software, hardware, or a combination thereof. For example, process700may be performed by data processing system100ofFIG. 1. Referring toFIG. 7, at block701, processing logic receives an intermediate result (e.g., intermediate representation with compiler injected vulnerability codes) generated by a compiler based on source code, wherein the intermediate result includes one or more vulnerability indicators indicating one or more lines of the source code being potentially vulnerable. At block702, processing logic performs a grey box fuzzing process on a first executable code generated from the intermediate result to generate a first set of seed inputs. At block703, processing logic calculates a vulnerability score for each of the seed inputs of the first set based on the vulnerability indicators for the lines of the source code reachable but has not been explored by the grey box fuzzing process. At block704, processing logic selects one of the seed inputs in the first set having a highest vulnerability score. At block705, processing logic performs a concolic execution using the selected seed input as priority, the concolic execution being performed on a second executable code generated from the intermediate result.

In one embodiment, the concolic executions generate a second set of seed inputs that caused a program flow control of the concolic execution to explore one or more branches of the source code not explored by the grey box fuzzing process. In another embodiment, processing logic further adds the second set of seed inputs to the first set of seed inputs, such that the one or more seed inputs of the second set are utilized by the grey box fuzzing process during a next iteration.

In one embodiment, calculating a vulnerability score for each of the seed inputs of the first set includes identifying a program control flow that has been explored by the grey box fuzzing process corresponding to the seed input, and calculating the vulnerability score for the seed input based on a number of vulnerability indicators reachable by the program control flow but that has not been explored by the grey box fuzzing process. In one embodiment, selecting one of the seed inputs in the first set having a highest vulnerability score comprises ordering the seed inputs of the first set based on their respective vulnerability scores to prioritize concolic executions for the first set of seed inputs.

In one embodiment, processing logic further identifies a plurality of basic blocks of code from the intermediate result. For each of the basic blocks, processing logic further determines a number of vulnerability indicators within the basic block, and generates a mapping table that maps a block identifier (ID) of each basic block to a number of vulnerability indicators associated with the basic block, wherein the mapping table is utilized to calculate a vulnerability score. In another embodiment, calculating a vulnerability score for each of the seed inputs of the first set includes building a program control flow graph (CFG) based on a program control flow of the intermediate result corresponding to the seed input, and summing the number of vulnerability indicators of all basic blocks reachable but unexplored by the program CFG to represent the vulnerability score for the seed input, wherein the summing comprises performing a lookup operation in the mapping table to determine a number of vulnerability indicators associated with the basic block. In one embodiment, the at least one of the vulnerability indicator includes an exception throw and catch (throw/catch) block inserted by the compiler, which when an associated line of source code violates a safety rule during execution, an exception is thrown and caught by an operating system.

FIG. 8is a block diagram illustrating an example of a data processing system which may be used with one embodiment of the invention. For example, system1500may represent any of data processing systems described above performing any of the processes or methods described above, such as, for example, a client device or a server described above, such as, for example, system101, as described above.

System1500can include many different components. These components can be implemented as integrated circuits (ICs), portions thereof, discrete electronic devices, or other modules adapted to a circuit board such as a motherboard or add-in card of the computer system, or as components otherwise incorporated within a chassis of the computer system.

Note also that system1500is intended to show a high level view of many components of the computer system. However, it is to be understood that additional components may be present in certain implementations and furthermore, different arrangement of the components shown may occur in other implementations. System1500may represent a desktop, a laptop, a tablet, a server, a mobile phone, a media player, a personal digital assistant (PDA), a Smartwatch, a personal communicator, a gaming device, a network router or hub, a wireless access point (AP) or repeater, a set-top box, or a combination thereof. Further, while only a single machine or system is illustrated, the term “machine” or “system” shall also be taken to include any collection of machines or systems that individually or jointly execute a set (or multiple sets) of instructions to perform any one or more of the methodologies discussed herein.

Processing module/unit/logic1528, components and other features described herein can be implemented as discrete hardware components or integrated in the functionality of hardware components such as ASICS, FPGAs, DSPs or similar devices. In addition, processing module/unit/logic1528can be implemented as firmware or functional circuitry within hardware devices. Further, processing module/unit/logic1528can be implemented in any combination hardware devices and software components.

The techniques shown in the figures can be implemented using code and data stored and executed on one or more electronic devices. Such electronic devices store and communicate (internally and/or with other electronic devices over a network) code and data using computer-readable media, such as non-transitory computer-readable storage media (e.g., magnetic disks; optical disks; random access memory; read only memory; flash memory devices; phase-change memory) and transitory computer-readable transmission media (e.g., electrical, optical, acoustical or other form of propagated signals—such as carrier waves, infrared signals, digital signals).