AUTOMATION OF SOFTWARE VERIFICATION

• US 20180018253A1
• Filed: 07/13/2017
• Published: 01/18/2018
• Est. Priority Date: 07/15/2016
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Blackberry Limited
• Inventors: MALTON, Andrew James, NEVILLE, Daniel Lewis
• Granted Patent: US 10,664,377 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 11/3604 Software analysis for verifying properties of programs byte-code verification G06F9/44589
• CPC Class Codes: G06F 11/3608 using formal methods, e.g. model checking, abstract interpretation theorem proving G06N5/013
• CPC Class Codes: G06F 11/3684 for test design, e.g. generating new test cases

Abstract

Systems, methods, and software can be used to automate software verifications. In some aspects, one or more application program interface (API) call pairs are generated based on a source code of a user module that invokes an API. Each of the one or more API call pairs comprises a first API call that invokes the API followed by a second API call that invokes the API. One or more fragments are generated based on the one or more API calls pairs. Each of the one or more fragments represents an execution sequence that includes at least one of the one or more API call pairs. The one or more fragments are verified.

Claims

1. A method, comprising:

generating, by a hardware processor, one or more application program interface (API) call pairs based on a source code of a user module that invokes an API, wherein each of the one or more API call pairs comprises a first API call that invokes the API followed by a second API call that invokes the API;

generating, by the hardware processor, one or more fragments based on the one or more API call pairs, wherein each of the one or more fragments represents an execution sequence that includes at least one of the one or more API call pairs; and

verifying, by the hardware processor, the one or more fragments.

2. The method of claim 1, further comprising:

generating, by the hardware processor, a prefix set based on the source code of the user module, wherein the prefix set includes at least one prefix in the user module; and

wherein the fragments are generated further based on the prefix set.

3. The method of claim 1, further comprising:

generating, by the hardware processor, a suffix set based on the source code of the user module, wherein the suffix set includes at least one suffix in the user module; and

wherein the fragments are generated further based on the suffix set.

4. The method of claim 1, wherein the one or more API call pairs are generated based on one or more arguments of the first API call or the second API call.

5. The method of claim 1, wherein the one or more fragments are verified using C Bounded Model Checker (CMBC).

6. The method of claim 1, further comprising:

determining that an assertion is violated; and

in response to determining that the assertion is violated, outputting a counterexample indicating a sequence of execution steps that violates the assertion.

7. The method of claim 6, further comprising:

logging a portion of the source code corresponding to the violated assertion in response to a user input.

8. A device, comprising:

at least one hardware processor; and

a non-transitory computer-readable storage medium coupled to the at least one hardware processor and storing programming instructions for execution by the at least one hardware processor, wherein the programming instructions, when executed, cause the at least one hardware processor to perform operations comprising;

generating one or more application program interface (API) call pairs based on a source code of a user module that invokes an API, wherein each of the one or more API call pairs comprises a first API call that invokes the API followed by a second API call that invokes the API;

generating one or more fragments based on the one or more API call pairs, wherein each of the one or more fragments represents an execution sequence that includes at least one of the one or more API call pairs; and

verifying the one or more fragments.

9. The device of claim 8, the operations further comprising:

generating a prefix set based on the source code of the user module, wherein the prefix set includes at least one prefix in the user module; and

wherein the fragments are generated further based on the prefix set.

10. The device of claim 8, the operations further comprising:

generating a suffix set based on the source code of the user module, wherein the suffix set includes at least one suffix in the user module; and

wherein the fragments are generated further based on the suffix set.

11. The device of claim 8, wherein the one or more API call pairs are generated based on one or more arguments of the first API call or the second API call.

12. The device of claim 8, wherein the one or more fragments are verified using C Bounded Model Checker (CMBC).

13. The device of claim 8, the operations further comprising:

determining that an assertion is violated; and

in response to determining that the assertion is violated, outputting a counterexample indicating a sequence of execution steps that violates the assertion.

14. The device of claim 13, the operations further comprising:

logging a portion of the source code corresponding to the violated assertion in response to a user input.

15. A non-transitory computer-readable medium storing instructions which, when executed, cause a computing device to perform operations comprising:

generating one or more application program interface (API) call pairs based on a source code of a user module that invokes an API, wherein each of the one or more API call pairs comprises a first API call that invokes the API followed by a second API call that invokes the API;

generating one or more fragments based on the one or more API call pairs, wherein each of the one or more fragments represents an execution sequence that includes at least one of the one or more API call pairs; and

verifying the one or more fragments.

16. The non-transitory computer-readable medium of claim 15, the operations further comprising:

generating a prefix set based on the source code of the user module, wherein the prefix set includes at least one prefix in the user module; and

wherein the fragments are generated further based on the prefix set.

17. The non-transitory computer-readable medium of claim 15, the operations further comprising:

generating a suffix set based on the source code of the user module, wherein the suffix set includes at least one suffix in the user module; and

wherein the fragments are generated further based on the suffix set.

18. The non-transitory computer-readable medium of claim 15, wherein the one or more API call pairs are generated based on one or more arguments of the first API call or the second API call.

19. The non-transitory computer-readable medium of claim 15, wherein the one or more fragments are verified using C Bounded Model Checker (CMBC).

20. The non-transitory computer-readable medium of claim 15, the operations further comprising:

determining that an assertion is violated; and

in response to determining that the assertion is violated, outputting a counterexample indicating a sequence of execution steps that violates the assertion.