Automation of software verification

• US 10,664,377 B2
• Filed: 07/13/2017
• Issued: 05/26/2020
• 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
• Primary Examiner(s): Morshed, Hossain M
• Application Number:
  US15/649,189
• Publication Number:
  US 20180018253A1
• Time in Patent Office: 1,048 Days
• Field of Search: None
• 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, wherein each of the one or more API call pairs comprises a first API call that invokes an associated API and a second API call that invokes the same associated 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, the fragments are generated further based on at least one of a prefix set or a suffix set, the prefix set includes at least one prefix in the user module, and the suffix set includes at least one suffix in the user module, and wherein the prefix set comprises an allowed prefix set and a required prefix set, and the suffix set comprises an allowed suffix set and a required suffix set, and wherein the allowed prefix set is obtained based on a union of first API calls of the one or more fragments, the allowed suffix set is obtained based on a union of last API calls of the one or more fragments, the required prefix set is obtained based on an intersection of the first API calls of the one or more fragments, and the required suffix set is obtained based on an intersection of the last API calls of the one or more fragments; and

determining, by the hardware processor, whether an assertion is violated by the one or more fragments.

2. 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.

3. The method of claim 1, wherein whether the assertion is violated by the one or more fragments is determined using C Bounded Model Checker (CBMC).

4. The method of claim 1, further comprising:

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

5. The method of claim 4, further comprising:

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

6. 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, wherein each of the one or more API call pairs comprises a first API call that invokes an associated API and a second API call that invokes the same associated 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, the fragments are generated further based on at least one of a prefix set or a suffix set, the prefix set includes at least one prefix in the user module, and the suffix set includes at least one suffix in the user module, and wherein the prefix set comprises an allowed prefix set and a required prefix set, and the suffix set comprises an allowed suffix set and a required suffix set, and wherein the allowed prefix set is obtained based on a union of first API calls of the one or more fragments, the allowed suffix set is obtained based on a union of last API calls of the one or more fragments, the required prefix set is obtained based on an intersection of the first API calls of the one or more fragments, and the required suffix set is obtained based on an intersection of the last API calls of the one or more fragments; and

determining whether an assertion is violated by the one or more fragments.

7. The device of claim 6, 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.

8. The device of claim 6, wherein whether the assertion is violated by the one or more fragments is determined using C Bounded Model Checker (CBMC).

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

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

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

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

11. 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, wherein each of the one or more API call pairs comprises a first API call that invokes an associated API and a second API call that invokes the same associated 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, the fragments are generated further based on at least one of a prefix set or a suffix set, the prefix set includes at least one prefix in the user module, and the suffix set includes at least one suffix in the user module, and wherein the prefix set comprises an allowed prefix set and a required prefix set, and the suffix set comprises an allowed suffix set and a required suffix set, and wherein the allowed prefix set is obtained based on a union of first API calls of the one or more fragments, the allowed suffix set is obtained based on a union of last API calls of the one or more fragments, the required prefix set is obtained based on an intersection of the first API calls of the one or more fragments, and the required suffix set is obtained based on an intersection of the last API calls of the one or more fragments; and

determining whether an assertion is violated by the one or more fragments.

12. The non-transitory computer-readable medium of claim 11, 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.

13. The non-transitory computer-readable medium of claim 11, wherein whether the assertion is violated by the one or more fragments is determined using C Bounded Model Checker (CBMC).

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

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