Granted Patent B2

US 12,277,230 · App. 17/168,079 · Granted Apr 15, 2025

Inventors: William James McCourt (West Lothian, GB); Niall Fitzgibbon (London, GB); Benjamin John Godwood (Chipping Norton, GB); Paul Compton Hirst (Tiverton, GB)

Assignee: BlackBerry Limited

G06F21/577G06F21/54

Abstract

Claims (50)

1. A method of symbolic analysis of a software program, the method comprising:

constructing, by at least one processor, a control flow graph (CFG), of a software program procedure, the CFG comprising nodes representing basic blocks reachable within the software program procedure, the basic blocks represented as respective functions from a first machine state on entry to a said basic block to a second machine state on exit from that basic block, wherein constructing the CFG comprises symbolically executing the basic blocks of the software program procedure to obtain side-effect free functions representing the basic blocks as symbolic changes of the machine states;

simplifying, by the at least one processor, the CFG to a single node representing the software program procedure as a function from an input machine state on entry to the software program procedure to an output machine state on exit from the software program procedure, wherein simplifying the CFG comprises at least one of merging basic blocks through symbolic substitution of the respective functions or replacing back edges within the CFG with explicit loop expressions, wherein simplifying the CFG comprises:

replacing return instructions within the CFG with links to respective nodes having a single exit; and

recursively processing another procedure and replacing a call to the another procedure in the CFG with a function representing a machine state change resulting from the another procedure;

comparing, by the at least one processor, said function to a rule set identifying one or more vulnerabilities based on one or more effects on the machine states; and

preventing, by the at least one processor, deployment of the software program procedure in response to determining a vulnerability within the software program procedure based on the comparing.

2. The method according to claim 1 , wherein the software program procedure comprises native application compiled code.

3. The method according to claim 1 , wherein simplifying the CFG comprises merging branches within the CFG by replacing the branches with a single node comprising an if-then-else function representing a machine state change resulting from the branches.

4. The method according to claim 1 , wherein simplifying the CFG comprises initially:

performing loop detection on the CFG;

identifying an inner-most loop;

replacing branches within the loop with a single node comprising an if-then-else function representing a machine state change resulting from the branches;

replacing the nodes and edges within said loop with a loop node comprising a function representing a machine state change resulting from said loop;

replacing said loop node with a non-loop node comprising a loop expression representing a machine state change on each iteration of the loop and a loop exit condition; and

iteratively identifying a next inner-most loop in the CFG and repeating said replacing steps until the CFG contains no loops.

5. The method of claim 1 wherein the comparing comprises matching the function to one or more rules of the rule set.

6. A non-transitory computer-readable media comprising instructions which when executed by at least one processor cause the at least one processor to perform operations comprising:

constructing a control flow graph (CFG) of a software program procedure, the CFG comprising nodes representing basic blocks reachable within the software program procedure, the basic blocks represented as respective functions from a first machine state on entry to a said basic block to a second machine state on exit from that basic block, wherein constructing the CFG comprises symbolically executing the basic blocks of the software program procedure to obtain side-effect free functions representing the basic blocks as symbolic changes of the machine states;

simplifying the CFG to a single node representing the software program procedure as a function from an input machine state on entry to the software program procedure to an output machine state on exit from the software program procedure, wherein simplifying the CFG comprises at least one of merging basic blocks through symbolic substitution of the respective functions or replacing back edges within the CFG with explicit loop expressions, wherein simplifying the CFG comprises replacing return instructions within the CFG with links to respective nodes having a single exit; and

recursively processing another procedure and replacing a call to the another procedure in the CFG with a function representing a machine state change resulting from the another procedure;

comparing said function to a rule set identifying one or more vulnerabilities based on one or more effects on the machine states; and

preventing deployment of the software program procedure in response to determining a vulnerability within the software program procedure based on the comparing.

7. The non-transitory computer-readable media according to claim 6 , wherein the software program procedure comprises native application compiled code.

8. The non-transitory computer-readable media according to claim 6 , wherein simplifying the CFG comprises merging branches within the CFG by replacing the branches with a single node comprising an if-then-else function representing a machine state change resulting from the branches.

9. The non-transitory computer-readable media according to claim 6 , wherein simplifying the CFG comprises initially:

performing loop detection on the CFG;

identifying an inner-most loop;

replacing branches within the loop with a single node comprising an if-then-else function representing a machine state change resulting from the branches;

replacing the nodes and edges within said loop with a loop node comprising a function representing a machine state change resulting from said loop;

replacing said loop node with a non-loop node comprising a loop expression representing a machine state change on each iteration of the loop and a loop exit condition; and

iteratively identifying a next inner-most loop in the CFG and repeating said replacing steps until the CFG contains no loops.

10. The non-transitory computer-readable media according to claim 6 , wherein the comparing comprises matching the function to one or more rules of the rule set.

11. A computing device comprising at least one processor and a memory, said memory containing instructions executable by said at least one processor to perform operations including:

constructing a control flow graph (CFG), for a software program procedure, the CFG comprising nodes representing basic blocks reachable within the software program procedure, the basic blocks represented as respective functions from a first machine state on entry to a said basic block to a second machine state on exit from that basic block, wherein constructing the CFG comprises symbolically executing the basic blocks of the software program procedure to obtain side-effect free functions representing the basic blocks as symbolic changes of the machine states;

simplifying the CFG to a single node representing the software program procedure as a function from an input machine state on entry to the software program procedure to an output machine state on exit from the software program procedure, wherein simplifying the CFG comprises at least one of merging basic blocks through symbolic substitution of the respective functions or replacing back edges within the CFG with explicit loop expressions, wherein simplifying the CFG comprises:

replacing return instructions within the CFG with links to respective nodes having a single exit; and

recursively processing another procedure and replacing a call to the another procedure in the CFG with a function representing a machine state change resulting from the another procedure;

comparing said function to a rule set identifying vulnerabilities based on effects on the machine states; and

preventing deployment of the software program procedure in response to determining a vulnerability within the software program procedure based on the comparing matching said function to a rule of said rule set.

12. The device according to claim 11 , wherein the software program procedure comprises native application compiled code.

13. The device according to claim 11 , wherein simplifying the CFG comprises merging branches within the CFG by replacing the branches with a single node comprising an if-then-else function representing a machine state change resulting from the branches.

14. The device according to claim 11 , wherein simplifying the CFG comprises initially:

performing loop detection on the CFG;

identifying an inner-most loop;

replacing branches within the loop with a single node comprising an if-then-else function representing a machine state change resulting from the branches;

replacing the nodes and edges within said loop with a loop node comprising a function representing a machine state change resulting from said loop;

replacing said loop node with a non-loop node comprising a loop expression representing a machine state change on each iteration of the loop and a loop exit condition; and

iteratively identifying a next inner-most loop in the CFG and repeating said replacing steps until the CFG contains no loops.

15. The device according to claim 11 , wherein the comparing comprises matching the function to one or more rules of the rule set.

Assignments (2)

Priority Claims (1)

Continuity (1)

References Cited (18)