Method and apparatus for paralleling and distributing static source code security analysis using loose synchronization

Abstract

A method of static source code analysis is provided. A forward search of source code is performed from each of a plurality of source nodes. A backward search of source code is performed from each of a plurality of sink nodes, wherein the forward search and the backward search are performed in parallel simultaneously. The progress of the forward search and the backward search are monitored to determine if the searches intersect at a common node. A vulnerability alert is generated when the monitoring determines that a forward search and a backward search reach a common node.

1 . A non-transitory computer program storage device embodying instructions executable by a processor to analyze source code, comprising:
 instruction code for performing by a computer system a forward search of source code from each of a plurality of source nodes;   instruction code for performing by the computer system a backward search of the source code from each of a plurality of sink nodes, wherein the forward search and the backward search are performed in parallel simultaneously;   instruction code for monitoring the progress of the forward search and the backward search by the computer system to determine if the forward search and the backward search intersect at a common node; and   instruction code for generating by the computer system a vulnerability alert when the monitoring determines that the forward search and the backward search reach the common node.   
     
     
         2 . The non-transitory computer program storage device of  claim 1 , further comprising instruction code for terminating by the computer system the forward search and the backward search when the monitoring determines that the forward searches and the backward search have reached a common node. 
     
     
         3 . The non-transitory computer program storage device of  claim 1 , wherein the monitoring is performed in parallel with the forward search and the backward search. 
     
     
         4 . A non-transitory computer program storage device embodying instructions executable by a processor for parallelizing and distributing static source code security analysis using loose synchronization, comprising:
 instruction code for breaking an original source code analysis into multiple independent sub-analyses that are tracked independently and computed periodically by a computer system, the multiple independent sub-analyses comprising a plurality of tasks comprising:
 forward tasks that correspond to source seeds; 
 backward tasks that correspond to sink seeds; 
 a chop task that corresponds to a source-sink pair with periodically computed samples; and 
 a witness creation task that corresponds to a source-sink pair with queries of partial data-flow graphs. 
   
     
     
         5 . The non-transitory computer program storage device of  claim 4 , wherein solutions for different seeds are computed by the computer system in parallel. 
     
     
         6 . The non-transitory computer program storage device of  claim 4 ,
 further comprising instruction code for determining by the computer system whether an intersection between solutions for a particular source-sink pair is empty,   wherein instruction code for finding by the computer system whether an intersection between solutions for a particular source-sink pair is empty comprises instruction code for read access into the solution which evolves monotonically per convergence requirements of a framework of abstract interpretation.   
     
     
         7 . The non-transitory computer program storage device of  claim 4 , wherein witness creation comprises read access into the corresponding slices without synchronization when a witness creation task is performed. 
     
     
         8 . A non-transitory computer program storage device embodying instructions executable by a processor to analyze source code comprising:
 instruction code executable by the processor for analyzing source code in parallel forward from source nodes and backwards from sink nodes;   instruction code executable by the processor for checking if forward searches and backwards searches reach same node(s); and   instruction code executable by the processor for producing a vulnerability alert whenever an intersection of the forward searches and backwards searches is detected.