A System And Method For Specifying And Executing Expressive Decision Tables Specifications
Abstract:
System and method for validating a specification associated with a software application and/or a hardware is disclosed. The specification comprising expected behaviour requirements specified in a specification language and the semantics in the tabular notation is received. In order to validate the specification, a string may be identified for the specification. The string may indicate characters conforming to the specification language. Upon identifying the string, a token may be generated using the string. The token may be a binary representation of the string. The token may be arranged into a data structure. The specification is checked to conform to the specification language. Two or more specifications specified in the specification language are merged. A test case is generated from the validated specification. The expected behaviour with the actual behaviour of the specification is validated.
Get Free WhatsApp Updates!
Notices, Deadlines & Correspondence
Nirmal Building, 9th Floor, Nariman Point, Mumbai 400021, Maharashtra, India
Inventors
1. KRISHNA, Goldsmith Murali
Tata Consultancy Services Limited,
Tata Research, Development and Design Centre (TRDDC), 54-B, Hadapsar Industrial Estate, Pune 411013, Maharashtra, India
2. SHROTRI, Ulka Aniruddha
Tata Consultancy Services Limited,
Tata Research, Development and Design Centre (TRDDC), 54-B, Hadapsar Industrial Estate, Pune 411013, Maharashtra, India
3. R, Venkatesh
Tata Consultancy Services Limited,
Tata Research, Development and Design Centre (TRDDC), 54-B, Hadapsar Industrial Estate, Pune 411013, Maharashtra, India
Specification
DESC:
FORM 2
THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENT RULES, 2003
COMPLETE SPECIFICATION
(See Section 10 and Rule 13)
Title of invention:
VALIDATING A SPECIFICATION ASSOCIATED WITH A SOFTWARE APPLICATION AND/OR A HARDWARE
Applicant
Tata Consultancy Services Limited
A Company Incorporated in India under The Companies Act, 1956
Having address:
Nirmal Building, 9th Floor,
Nariman Point, Mumbai 400021,
Maharashtra, India
The following specification particularly describes the invention and the manner in which it is to be performed.
TECHNICAL FIELD
[001] The present invention relates to a field of specifying requirements for a software application and/or a hardware. More particularly, the present invention relates to a system and method for validating a specification associated with a software application and/or a hardware.
BACKGROUND OF THE INVENTION
[002] Software applications are increasingly becoming critical in modern life. It is important to provide an adequate quality and minimize defects in software applications. Generally, in order to verify the software applications, software application may be tested before its execution. In order to test the software application, several methods have been proposed. Test automation is one of the methods used for software testing. Test automation is used to automate the execution of software tests and to compare actual outcome with predicted outcome of the software test results.
[003] Test automation requires an automated test execution and results verification, termed as an automated test oracle. The automated test oracle is a reliable source used for expected outputs. The automated test oracle may be used to verify test case results that are executed on the software application under test. In order to verify behaviour of the software application, testers may require the test oracle for reliable expected behaviour of the software application. The automated test oracle may provide an output for a given input specified in the software application to verify the actual results generated by the software application.
[004] In general, for automating the test oracle of reactive systems, a specification notation may be used to specify behavioural requirements for the reactive systems. In one example, the reactive system may include an automotive application. In one example, the automotive application may comprise sensors and actuators. The reactive systems may interact with their environment such as via sensors (inputs) and actuators (outputs). The behavioural requirements for the reactive systems are traditionally described using state-based or stream-based paradigms. In the state-based paradigm, the reaction of the automotive application to an input value is described based on current state of the automotive application. In the stream-based paradigm, the reaction of the automotive application is based on the pattern of stream of input values.
[005] After specifying the behavioural requirements, creating test cases that cover the behavioural requirements is a challenging task and verifying the test results manually is tedious. In order to overcome issues presented above, automated test oracles may be used. However, when the automated test oracle is used, the systems/reactive systems require users to specify the behavioural requirements formally. Further, current specification notations are not user friendly while capturing the behavioural requirements and automated test oracles require specification of the behavioural requirements in formal specification notation.
[006] Existing specification notations for automating the test oracles may include Statecharts, SCR, timing diagrams, and I/O Stream-based tables. Statecharts is a graphical state-based notation as disclosed in “Statecharts: A visual formalism for complex systems,” Science of Computer Programming, 1987 by D. Harel. The specification notations such as SCR are tabular notations, but are similar to the Statecharts. For sequence oriented specification requirements, the user may have to analyze and convert the specification requirements to state-based form. Further, timing diagram is a graphical and stream-based notation as disclosed in “A graphic language based on timing diagrams,” in Proceedings of the 13th Conference on Foundations of Software Technology and Theoretical Computer Science. London, UK, by C. Antoine, B. L. Goff, and J.-E. Pin. Although, timing diagram provides support for stream-based requirements, they are not suitable for state-based requirements. The I/O stream-based tables are stream-based requirements and are also tabular as disclosed in “Behavioural specification of reactive systems using stream-based I/O tables,” Software and Systems Modeling, 2011, by J. Thyssen and B. Hummel. However, the I/O Stream-based tables are not suitable for state-based requirements. Therefore, the above techniques result in the specifications that are not feasible to relate to the requirements of the system/reactive system, and the specifications are not relatable to the testers in viewing the requirements.
SUMMARY
[007] This summary is provided to introduce concepts related to systems and methods for validating a specification associated with a software application and/or a hardware and the concepts are further described below in the detailed description. This summary is not intended to identify essential features of the claimed subject matter nor is it intended for use in determining or limiting the scope of the claimed subject matter.
[008] In one implementation, a method for validating a specification associated with a software application and/or a hardware is disclosed. The method comprises receiving the specification comprising expected behaviour requirements in a specification language and semantics in a tabular notation. The expected behaviour requirements indicate a behaviour expected from the software application and/or the hardware. The method further comprises identifying a string comprising one or more from the specification. The string indicates the one or more characters conforming to the specification language. The method further comprises generating a token using the string. The token is a binary representation of the string. The method further comprises arranging the token into a data structure. The data structure is indicative of an actual behaviour of the software application and/or the hardware. The method further comprises checking the specification conforming to the specification language. The specification is checked in order to generate a validated specification. The receiving, the identifying, the arranging, and the checking are performed by a processor using programming instructions stored in a memory. The method further comprises generating a test case from the validated specification. The method further comprises validating the expected behaviour with the actual behaviour of the specification. The method further comprises merging two or more of the specifications specified in the specification language.
[009] In one implementation, a system for validating and evaluating a specification associated with a software application and/or a hardware is disclosed. The system comprises a processor and a memory coupled to the processor. The processor is capable of executing a plurality of modules stored in the memory. The plurality of modules comprises a reception module to receive the specification comprising expected behaviour requirements specified in a specification language and semantics in a tabular notation. The expected behaviour requirements indicate behaviour expected from the software application and/or the hardware. The plurality of modules further comprises a lexer to identify a string comprising one or more characters from the specification. The string indicates the one or more characters conforming to the specification language. The lexer further generates a token using the string. The token is a binary representation of the string. The plurality of modules further comprises a parser to create an intermediate representation of the specification. The parser further arranges the token into a data structure. The data structure is indicative of an actual behaviour of the software application and/or the hardware. The plurality of modules further comprises a checking module to check the specification conforming to the specification language. The plurality of modules further comprises an analyzing module to generate a test case for a row in the validated specification. Further, the analyzing module may validate the expected behaviour with the actual behaviour specified in the specification. Further, the analyzing module merges two or more of the validated specifications specified in the specification language.
[010] In one implementation, a non-transitory computer readable medium embodying a program executable in a computing device for validating a specification associated with a software application and/or a hardware is disclosed. The program comprises a program code for receiving the specification comprising expected behaviour requirements specified in a specification language and semantics in a tabular notation. The expected behaviour requirements indicate a behaviour expected from the software application and/or the hardware. The program further comprises a program code for identifying a string comprising one or more characters from the specification language. The string indicates the one or more characters conforming to the specification language. The program further comprises a program code for generating a token using the string. The token is a binary representation of the string. The program further comprises a program code for arranging the token into a data structure. The data structure is indicative of an actual behaviour of the software application and/or the hardware. The program further comprises a program code for checking the specification conforming to the specification language. The specification is checked in order to generate a validated specification.
BRIEF DESCRIPTION OF DRAWINGS
[011] The detailed description is provided with reference to the accompanying figures. In the figures, the left-most digit(s) of a reference number identifies the figure in which the reference number first appears. The same numbers are used throughout the drawings to refer like/similar features and components.
[012] FIG. 1 illustrates a network implementation of a system for validating a specification associated with a software application and/or a hardware, in accordance with an embodiment of the present disclosure.
[013] FIG. 2 illustrates the system, in accordance with an embodiment of the present disclosure.
[014] FIG. 3 illustrates a method for merging two or more specifications, in accordance with an embodiment of the present disclosure.
[015] FIG. 4 illustrates a method for validating a specification associated with a software application and/or a hardware, in accordance with an embodiment of the present disclosure.
DETAILED DESCRIPTION
[016] The present disclosure relates to systems and methods for validating a specification associated with a software application and/or a hardware. The specification may be used to specify expected behaviour requirements for a reactive system. The reactive system may interact with their environment via sensors (inputs) and actuators (outputs). The interactions with their environment are described using a combination of natural language, state-based paradigms, and stream-based paradigms. Examples of the state-based paradigms include state transition tables and stream-based paradigms include timing diagrams. Generally, the specification is specified that follows the specification language to specify the behaviour requirements. The specification may be specified in the specification language in a tabular notation. The specification language may enable translation of the behaviour requirements into a formal specification. The specification may comprise the expected behaviour requirements specified in the specification language and semantics in the tabular notation. The expected behaviour requirements indicate a behaviour expected from the software application and/or the hardware.
[017] The software application and/or the hardware may be an automotive application. In one embodiment, the behaviour requirements of the reactive systems may be described/specified using a state based or a stream based paradigm. In the state based paradigm, behaviour requirements based on reaction of the reactive systems to an event may be described/specified based on current/present state of the reaction system. Further, in the stream based paradigm, behaviour requirements based on reaction of the reactive systems to an event pattern may not be described/specified based on the state of the reaction system.
[018] The specification specified may support/combine the semantics that may be similar to the state based and the stream based paradigm for specifying the requirements. The specification comprising expected behaviour requirements specified in the specification language and the semantics in the tabular notation is received. In order to check the specification conforming to the specification language, a string may be identified from the specification. The string may comprise one or more characters. The string may indicate the one or more characters conforming to the specification language. Upon identifying the string, a token may be generated using the string. The token may be a binary representation of the string. The token may be arranged into a data structure. The data structure may be indicative of an actual behaviour of the software application and/or the hardware. The specification conforming to the specification language may be checked based on the data structure. The specification may be checked in order to generate a validated specification. The validated specification may be used to generate test cases and verify test results. Further, the expected behaviour may be validated with the actual behaviour as specified in the specification. Further, one or more of the specifications specified in the specification language may be merged.
[019] While aspects of described system and method for validating a specification associated with a software application and/or a hardware may be implemented in any number of different computing systems, environments, and/or configurations, the embodiments are described in the context of the following exemplary system.
[020] Referring now to FIG. 1, a network implementation 100 of a system 102 for validating a specification associated with a software application and/or a hardware is illustrated, in accordance with an embodiment of the present disclosure. The system 102 may receive the specification comprising expected behaviour requirements specified in a specification language and semantics in a tabular notation. From the specification received, the system 102 may identify a string. The string may comprise one or more characters from the specification. The string may be indicative of the characters conforming to the specification language. Upon identifying the string, the system 102 may generate a token using the string. The token generated may be a binary representation of the string. Further, the system 102 may arrange the token into a data structure. The data structure may indicate an actual behaviour of the software application and/or the hardware. The system 102 may check the specification with the specification language.
[021] Although the present disclosure is explained by considering a scenario that the system 102 is implemented as an application on a server. It may be understood that the system 102 may also be implemented in a variety of computing systems, such as a laptop computer, a desktop computer, a notebook, a workstation, a mainframe computer, a server, a network server, and the like. It will be understood that the system 102 may be accessed by multiple users through one or more user devices 104-1, 104-2…104-N, collectively referred to as user devices 104 hereinafter, or applications residing on the user devices 104. Examples of the user devices 104 may include, but are not limited to, a portable computer, a personal digital assistant, a handheld device, and a workstation. The user devices 104 are communicatively coupled to the system 102 through a network 106.
[022] In one implementation, the network 106 may be a wireless network, a wired network or a combination thereof. The network 106 can be implemented as one of the different types of networks, such as intranet, local area network (LAN), wide area network (WAN), the internet, and the like. The network 106 may either be a dedicated network or a shared network. The shared network represents an association of the different types of networks that use a variety of protocols, for example, Hypertext Transfer Protocol (HTTP), Transmission Control Protocol/Internet Protocol (TCP/IP), Wireless Application Protocol (WAP), and the like, to communicate with one another. Further the network 106 may include a variety of network devices, including routers, bridges, servers, computing devices, storage devices, and the like.
[023] Referring now to FIG. 2, the system 102 is illustrated in accordance with an embodiment of the present disclosure. In one embodiment, the system 102 may include at least one processor 202, an input/output (I/O) interface 204, and a memory 206. The at least one processor 202 may be implemented as one or more microprocessors, microcomputers, microcontrollers, digital signal processors, central processing units, state machines, logic circuitries, and/or any devices that manipulate signals based on operational instructions. Among other capabilities, the at least one processor 202 is configured to fetch and execute computer-readable instructions stored in the memory 206.
[024] The I/O interface 204 may include a variety of software and hardware interfaces, for example, a web interface, a graphical user interface, and the like. The I/O interface 204 may allow the system 102 to interact with a user directly or through the user devices 104. Further, the I/O interface 204 may enable the system 102 to communicate with other computing devices, such as web servers and external data servers (not shown). The I/O interface 204 may facilitate multiple communications within a wide variety of networks and protocol types, including wired networks, for example, LAN, cable, etc., and wireless networks, such as WLAN, cellular, or satellite. The I/O interface 204 may include one or more ports for connecting a number of devices to one another or to another server.
[025] The memory 206 may include any computer-readable medium known in the art including, for example, volatile memory, such as static random access memory (SRAM) and dynamic random access memory (DRAM), and/or non-volatile memory, such as read only memory (ROM), erasable programmable ROM, flash memories, hard disks, optical disks, and magnetic tapes. The memory 206 may include modules 208 and system data 230.
[026] The modules 208 include routines, programs, objects, components, data structures, etc., which perform particular tasks or implement particular abstract data types. In one implementation, the modules 208 may include a reception module 210, a lexer 212, a parser 214, a checking module 216, an analyzing module 218, and other modules 220. The other modules 220 may include programs or coded instructions that supplement applications and functions of the system 102.
[027] The system data 230, amongst other things, serves as a repository for storing data processed, received, and generated by one or more of the modules 208. The system data 230 may also include a system database 232 and other data 234. The other data 234 may include data generated as a result of the execution of one or more modules in the other modules 220.
[028] In one implementation, at first, a user may use the client device 104 to access the system 102 via the I/O interface 204. The working of the system 102 may be explained in detail using FIG. 2, explained below. The system 102 may be used to validate a specification associated with a software application and/or a hardware. In one example, the software application and/or the hardware may comprise an automotive application. In another example, the software application and/or the hardware may comprise an avionic application. In one example, the automotive application may comprise a wiper of a car.
[029] In order to validate the specification associated with the software application and/or the hardware, at first, the system 102 may receive the specification comprising expected behaviour requirements in a specification language and semantics in a tabular notation. In one implementation, the system 102 may employ the reception module 210 to receive the specification. The specification may comprise requirements specified in the specification language (Expressive Decision Table (EDT)). In other words, the specification may indicate behaviour description/requirements and properties of the software application and/or the hardware specified in the specification language. In one example, the specification may specify description/requirements of the behaviour and the properties of the automotive application.
[030] In order to understand the requirements specified for the software application and/or the hardware, an example may be used. In one non-limiting example, the requirements may be specified for a wiper of the car. The requirements for the wiper of the car may be presented as:
1. If the ignition and wiper switch are on and there is no fault in the wiper, then send a
a wipe message to the wiper.
2. If wiper is vibrating between park and notpark position, that is, if the wiper is stuck, send a dontwipe message to the wiper. Further, wiper may be considered to be stuck if the wiper switches between park and notpark position thrice within a second.
3. To reset the wiper error, while ignition is on, the wiper switch needs to be switched on and off within half a second.
[031] For the example presented above, the requirements specified at first may be based on a state of ignition and wiper switch that may be defined in a state-based paradigm. Further, the requirements specified at second may be based on a pattern of input values read by a wiper position sensor that may be defined in a stream-based paradigm. Further the requirements specified at third may combine the state of the ignition and the input pattern of the wiper switch that may be based on the state-based and stream-based paradigm.
[032] The specification may be specified for the above example in a tabular notion. The specification may comprise at least one of sequence of input and output events, conditions, and timing constraints. The input and output events and the timing constraints specified in the tabular notation are explained using the example. In one non-limiting example, Table 1 may be used as an example to illustrate the specification specified for the requirements presented above.
Table 1: Requirements specified for the automotive application
sno in ignition in wiperswitch in parksensor in error out wipercmd out error
1 on on false wipe
2 (park;notpark)
{= 3}{=1 s} dontwipe true
3 on true
on{=0.5 s};off false
Table 1
[033] Table 1 shows the specification of the wiper specified in the specification language in the tabular notation. From the specification, a header of the table specifies the input ports and the output ports. Referring to Table 1, the header of the table may specify four input ports - ignition, wiperswitch, parksensor and error and two output ports wipercmd and error. The port with the name error is an input and output (I/O) port. The Table 1 comprises three row-sequences where the first two row-sequences comprises only one row each and the third has two rows for rows three and four. For the purpose of illustration, the third row is depicted by a sequence number 3. Each requirement presented in the example may be specified in the table as a separate row-sequence and may be interpreted as follows:
1. If values at ports ignition and wiperswitch are on and the value at error is false then the output wipe at wipercmd port as soon as all inputs arrive.
2. If park followed by notpark repeats thrice within one second at the parksensor port, the output dontwipe at the wipercmd port and true at the error port.
3. If the last value for ignition is on, and error is true, and then wiperswitch has value on followed by off within 0.5 seconds, then output false at the error port.
[034] The specification may comprise one or more tables where the headers of the column may specify the input and output ports and the rows may specify a relationship between input and output values. Further, each cell in a row comprises of a regular expression that is used to match input streams at that port. The input values may arrive as a stream at the input ports at discrete time units and the output values may be generated as a stream at the output ports at discrete time units. In one implementation, rules for the regular expression pattern may be described using few examples. In one example, the pattern on matches, if the last value seen is on. In another example, on{=0.5 s} matches if the last value seen is on and not more than 0.5 seconds have passed since on was seen. In one embodiment, the regular expressions <, =, = and > may be applied. In another example, on{=0.5s};off matches if the last two values are on followed by off and off occurs within 0.5 seconds of on. In another example, (park;notpark){=3}{=1s} matches if the pattern park followed by notpark repeats thrice within 1 second. In another example, an empty cell may match any value if all corresponding cells before it in the row sequence are also empty, otherwise the empty cell may not match with any other cell. For the example as shown in Table 1, in the third row-sequence table, both cells of the parksensor may match any value. Further, in the second row of the table, the cell for ignition may match only if there is no value.
[035] In addition, the first row of any row-sequence matches if each input cell of that row matches. Further, subsequent rows may match when all rows before it match and all its input cells also match. If a row matches, the automotive application may give output values as specified by the patterns of that row’s output cells. Further, if a row has matched, if no further inputs arrive at the input ports, the row may continue to match but the output may not be generated.
[036] In one exemplary embodiment, the rules for matching the input and the output considering the example in Table 1 may be presented. For the specification presented in Table 1, consider a set of input strings at the end of four time units as wiperswitch = [on e e e], ignition = [e on e e] and error = [false e e e], where e represents absence of any value at that time. At time 2, row-sequence one matches and the value wipe is output to wipercmd at time 3 and hence its output stream will be [e e wipe e]. Further, the row-sequence continues to match at time 3 and there is no output at time 4. This is because the row-sequence is an extension of the previous match with no further inputs.
[037] In another non-limiting example, consider a second set of input strings at the end of three time units as ignition = [on e e], error = [true e e] and wiperswitch = [e on off]. At time 1, the first row of the row-sequence three matches and at time 3 and the second row matches. For the above consideration, it may be assumed that each time unit may correspond to 100ms. For the above example, the considerations may result in false being the output to error and the corresponding string may become [true e e false].
[038] In one implementation, syntax and the semantics for the specification specified is explained. At first, the syntax for the specification is explained. Each cell in a table may either be empty or may comprise the pattern expression. In one example, the syntax for the pattern expression may be presented as:
? : = ? | ?; ?| ?{op t s}| ? { op n}| (?) where
- ? is a value
- ; denotes sequence
- op? {<, =, =, =, >}
- t is a floating point constant for time
- s indicates seconds
- n is an integer constant for multiplicity
[039] The semantics may define consistency of given input strings and output strings for the specification. The specification may employ a discrete unit of time and therefore at any given time t, a string may be present at each port. The string at each port may comprise the values from the port’s domain or e. e represents the absence of any value at that time. The semantics of the specification may define which rows of a given table matches the input strings at a given time t. The semantics for the row that are matching may assume that cell matching predicates that are standard regular expression when the pattern-matching predicates. Each value ? in a pattern that may be translated to ? • e* and a time expression is translated to an appropriate en. The first row of the row-sequence may be matched if all the cells of the cells are matched. Further, the subsequent rows are matched if all previous rows match and the current row also matches. The matching of the row at time t may be defined as:
mr (rji, t) if j= 1
mr (rji, t) =
m*r (rji, t) otherwise
m1r (rji, t) = ?c • mx(stc, eicj) ? ?(c)
m*r (rji, t) =
?t1 < t • mr(rj-1i, t1) ?
?c• ? -(c) ?
?t2.t1