System and method for deriving a process-based specification

• US 7,543,274 B2
• Filed: 02/25/2004
• Issued: 06/02/2009
• Est. Priority Date: 12/22/2003
• Status: Active Grant

• Current Assignee: The United States of America As Represented By The Secretary of Agriculture
• Original Assignee: United States Of America As Represented By The Administrator Of The National Aeronautics And Space Administration
• Inventors: Rash, James Larry, ROUFF, Christopher A., Hinchey, Michael Gerard
• Primary Examiner(s): Zhen, Wei Y
• Assistant Examiner(s): DENG, ANNA CHEN
• Application Number:
  US10/789,028
• Publication Number:
  US 20050138602A1
• Time in Patent Office: 1,924 Days
• Field of Search: 717100-109, 717169-170, 717/123
• US Class Current: 717/123
• CPC Class Codes: G06F 8/20 Software design
• CPC Class Codes: G06F 8/30 Creation or generation of source code

Abstract

A system and method for deriving a process-based specification for a system is disclosed. The process-based specification is mathematically inferred from a trace-based specification. The trace-based specification is derived from a non-empty set of traces or natural language scenarios. The process-based specification is mathematically equivalent to the trace-based specification. Code is generated, if applicable, from the process-based specification. A process, or phases of a process, using the features disclosed can be reversed and repeated to allow for an interactive development and modification of legacy systems. The process is applicable to any class of system, including, but not limited to, biological and physical systems, electrical and electro-mechanical systems in addition to software, hardware and hybrid hardware-software systems.

Claims

1. A method for deriving a process-based specification for a system, comprising:

deriving a trace-based specification from a non-empty set of traces by a processor, wherein a trace is a sequence of actions expressed as strings representing a history of an execution of a process;

mathematically inferring the process-based specification from the trace-based specification, wherein mathematically inferring includes applying Laws of Concurrency in reverse to a set of system traces to determine the process-based specification, wherein the process-based specification is mathematically equivalent to the trace-based specification, and whereby the Laws of Concurrency are algebraic laws that (a) allow at least one process to be manipulated and analyzed, (b) permit formal reasoning about equivalences between processes, and (c) determine traces from the at least one process;

generating the process-based specification using an inference engine, wherein the inference engine iteratively applies a set of rules to a set of data representing a problem to determine a solution to the problem by logical manipulation and analysis of the set of data; and

analyzing the process-based specification to examine possible implementations of the process-based specification in different configurations, whereby analyzing includes identifying at least one equivalent alternative process-based specification and characterizing differences between the process-based specification and the at least one alternative process-based specification, wherein differences include number of processes, deterministic behavior, and competition for resources.

2. The method of claim 1, wherein the process-based specification is provably equivalent to the trace-based specification.

3. The method of claim 1, wherein the Laws of Concurrency are used by the inference engine to generate the process-based specification.

4. The method of claim 3, wherein the laws of concurrency are reversed by embedding the Laws of Concurrency in the inference engine.

5. The method of claim 4, wherein the embedding is syntactic or shallow.

6. The method of claim 4, wherein the embedding is semantic or deep.

7. The method of claim 3, wherein the Laws of Concurrency are reversed so that an equivalent process expression is output in response to a given input of at least one trace.

8. The method of claim 7, wherein multiple process expressions are given as output in response to inputs of the at least one trace.

9. The method of claim 1, wherein the various possible implementations of the process-based specification are based on transformations of the process-based specification by applying the Law of Concurrency to derive various implementations.

10. The method of claim 9, wherein the various equivalent implementations are mathematically equivalent to the process-based specification.

11. The method of claim 10, wherein the various equivalent implementations are provable equivalent to the process-based specification.

12. The method of claim 11, wherein multiple correct process-based specifications are possible.

13. The method of claim 12, further comprising:

deciding which of the multiple correct process-based specifications are most appropriate.

14. The method of claim 13, wherein the process-based specification is used as a basis for generation of alternate representations.

15. The method of claim 14, wherein the alternate representations are sets of instructions.

16. The method of claim 1, wherein the set of traces is a set of sequences of events or activities specific to an application domain.

17. The method of claim 1, wherein the set of traces is derived by pre-processing a set of scenarios given as input by a user to a context sensitive editor.

18. The method of claim 17, wherein the set of scenarios is natural language text describing intended system behavior, and the elements of the set of traces are sequences of events or activities in a given application domain.

19. The method of claim 18, wherein the set of scenarios is represented by various graphical notations.

20. The method of claim 1, wherein the deriving step is repeated.

21. The method of claim 1, wherein the inferring step is repeated.

22. The method of claim 1, further comprising:

reverse engineering an existing system using the deriving step and the inferring step, whereby reverse engineering includes analyzing a process-based specification and applying the Laws of Concurrency using an inference engine having domain knowledge to infer a set of traces equivalent to the process-based specification and to derive a set of scenarios for the system equivalent to the process-based specification, wherein the scenarios are natural language text that describes the system'"'"'s actions in response to incoming data and the internal goals of the system.

23. The method of claim 1, further comprising:

reverse engineering an existing system back to a set of traces using the deriving step and the inferring step, whereby reverse engineering includes analyzing a process-based specification and applying the Laws of Concurrency using an inference engine having domain knowledge to infer a set of traces equivalent to the process-based specification and to derive a set of scenarios for the system equivalent to the process-based specification, wherein the scenarios are natural language text that describes the system'"'"'s actions in response to incoming data and the internal goals of the system.

24. a system adapted for deriving a process-based specification, comprising:

at least one natural language scenario;

a computer-readable medium having instructions stored thereon for deriving a trace-based specification from the at least one natural language scenario;

an inference engine for mathematically inferring the process-based specification from the trace-based specification, wherein mathematically inferring includes applying Laws of Concurrency in reverse to a set of system traces to determine the process-based specification, wherein the process-based specification is mathematically equivalent to the trace-based specification, and whereby the Laws of Concurrency are algebraic laws that (a) allow at least one process to be manipulated and analyzed, (b) permit formal reasoning about equivalences between processes, and (c) determine traces from the at least one process;

a generating engine for generating the process-based specification using an inference engine, wherein the inference engine iteratively applies a set of rules to a set of data representing a problem to determine a solution to the problem by logical manipulation and analysis of the set of data; and

an analyzing engine for analyzing the process-based specification to examine possible implementations of the process-based specification in different configurations, whereby analyzing includes identifying at least one equivalent alternative process-based specification and characterizing differences between the process-based specification and the at least one alternative process-based specification, wherein differences include number of processes, deterministic behavior, and competition for resources.

25. A system adapted for deriving a process-based specification, comprising:

a non-empty set of traces;

a computer-readable medium having instructions stored thereon for deriving a trace-based specification from the set of traces, wherein a trace is a sequence of actions expressed as strings representing a history of an execution of a process;

an inference engine for mathematically inferring the process-based specification from the trace-based specification, wherein mathematically inferring includes applying Laws of Concurrency in reverse to a set of system traces to determine the process-based specification, wherein the process-based specification is mathematically equivalent to the trace-based specification, and whereby the Laws of Concurrency are algebraic laws that (a) allow at least one process to be manipulated and analyzed, (b) permit formal reasoning about equivalences between processes, and (c) determine traces from the at least one process;

a generating engine for generating the process-based specification using an inference engine, wherein the inference engine iteratively applies a set of rules to a set of data representing a problem to determine a solution to the problem by logical manipulation and analysis of the set of data; and

an analyzing engine for analyzing the process-based specification to examine possible implementations of the process-based specification in different configurations, whereby analyzing includes identifying at least one equivalent alternative process-based specification and characterizing differences between the process-based specification and the at least one alternative process-based specification, wherein differences include number of processes, deterministic behavior, and competition for resources.

26. A method for deriving a process-based specification for a system, wherein the system performs actions, comprising:

receiving at least one natural language scenario describing the actions;

generating a trace-based specification from the at least one natural language scenario by a processor;

mathematically inferring the process-based specification from the trace-based specification, wherein mathematically inferring includes applying Laws of Concurrency in reverse to a set of system traces to determine the process-based specification, wherein the process-based specification is mathematically equivalent to the actions defined above, whereby the Laws of Concurrency are algebraic laws that (a) allow at least one process to be manipulated and analyzed, (b) permit formal reasoning about equivalences between processes, and (c) determine traces from the at least one process;

generating the process-based specification using an inference engine, wherein the inference engine iteratively applies a set of rules to a set of data representing a problem to determine a solution to the problem by logical manipulation and analysis of the set of data; and

analyzing the process-based specification to examine possible implementations of the process-based specification in different configurations, whereby analyzing includes identifying at least one equivalent alternative process-based specification and characterizing differences between the process-based specification and the at least one alternative process-based specification, wherein differences include number of processes, deterministic behavior, and competition for resources.