Method, product, and system for solving arbitrary constraint satisfaction problems
Disclosed is an approach for solving arbitrary constraint satisfaction problems. In some embodiments, the approach includes a process to generate a software representation of what is possible based on a system corresponding to the constraint satisfaction problem. The software representation comprises a state machine where different states can be reached using respective transitions or properties which are possible as determined based on a current state of the system and parameters thereof whether global or otherwise.
1 . A method comprising:
identifying data corresponding to a constraint satisfaction problem associated with a system, wherein the data represents a plurality of variables and a plurality of constraints for the constraint satisfaction problem;
generating a software representation of the system based on the data, wherein the software representation comprises the plurality of variables, the plurality of constraints, and one or more crash statements inserted into the software representation for causing a crash when the software representation determines that an input satisfies the plurality of constraints; and
analyzing the software representation to identify one or more solutions to the constraint satisfaction problem associated with the system using respective inputs of a plurality of inputs at least by:
generating, by a fuzzer, a respective input to be processed by the software representation,
mapping the respective input generated by the fuzzer to the plurality of variables in the software representation,
traversing the software representation to execute one or more statements based on at least a subset of the plurality of variables to determine whether the respective input satisfies the plurality of constraints, and
when the respective input satisfies the constraint satisfaction problem, execution of the one or more statements based on at least a subset of the plurality of variables causes execution of a crash statement of the one or more crash statements inserted into the software representation.
2 . The method of claim 1 , wherein the software representation comprises a source code representation or an executable compiled from the source code representation and represents a plurality of states and possible transitions between states.
3 . The method of claim 1 , wherein the software representation comprises a source code representation or an executable compiled from the source code representation and encapsulates a bitmap representing a plurality of states and transitions between states.
4 . The method of claim 1 , wherein the software representation represents a plurality of global parameters and access to a plurality of resources depends upon at least respective sets of one or more global parameters of the plurality of global parameters.
5 . The method of claim 1 , wherein the system comprises information pertaining to interrelationships between entities.
6 . The method of claim 1 , wherein inputs to one or more instances of the software representation are generated by respective fuzzers.
7 . The method of claim 6 , wherein a plurality of fuzzers operate in parallel to generate inputs to respective instances of the software representation.
8 . A non-transitory computer readable medium having stored thereon a set of instructions, the set of instructions, when executed by a processor, causing a set of acts comprising:
identifying data corresponding to a constraint satisfaction problem associated with a system, wherein the data represents a plurality of variables and a plurality of constraints for the constraint satisfaction problem;
generating a software representation of the system based on the data, wherein the software representation comprises the plurality of variables, the plurality of constraints, and one or more crash statements inserted into the software representation for causing a crash when the software representation determines that an input satisfies the plurality of constraints; and
analyzing the software representation to identify one or more solutions to the constraint satisfaction problem associated with the system using respective inputs of a plurality of inputs at least by:
generating, by a fuzzer, a respective input to be processed by the software representation,
mapping the respective input generated by the fuzzer to the plurality of variables in the software representation,
traversing the software representation to execute one or more statements based on at least a subset of the plurality of variables to determine whether the respective input satisfies the plurality of constraints, and
when the respective input satisfies the constraint satisfaction problem, execution of the one or more statements based on at least a subset of the plurality of variables causes execution of a crash statement of the one or more crash statements inserted into the software representation.
9 . The non-transitory computer readable medium of claim 8 , wherein the software representation comprises a source code representation or an executable compiled from the source code representation and represents a plurality of states and possible transitions between states.
10 . The non-transitory computer readable medium of claim 8 , wherein the software representation comprises a source code representation or an executable compiled from the source code representation and encapsulates a bitmap representing a plurality of states and transitions between states.
11 . The non-transitory computer readable medium of claim 8 , wherein the software representation represents a plurality of global parameters and access to a plurality of resources depends upon at least respective sets of one or more global parameters of the plurality of global parameters.
12 . The non-transitory computer readable medium of claim 8 , wherein the system comprises information pertaining to interrelationships between entities.
13 . The non-transitory computer readable medium of claim 8 , wherein inputs to one or more instances of the software representation are generated by respective fuzzers.
14 . The non-transitory computer readable medium of claim 13 , wherein a plurality of fuzzers operate in parallel to generate inputs to respective instances of the software representation.
15 . A computing system comprising:
a memory storing a set of instructions; and
a processor to execute the set of instructions to perform a set of acts comprising:
identifying data corresponding to a constraint satisfaction problem associated with a system, wherein the data represents a plurality of variables and a plurality of constraints for the constraint satisfaction problem;
generating a software representation of the system based on the data, wherein the software representation comprises the plurality of variables and the plurality of constraints; and
analyzing the software representation to identify possible solutions to the constraint satisfaction problem associated with the system using a fuzzer to generate inputs to the software representation, wherein the inputs generated by the fuzzer are mapped to at least one of the plurality of variables and the software representation is used to determine whether an input satisfies corresponding constraints of the plurality of constraints.
16 . The computing system of claim 15 , wherein the software representation comprises a source code representation or an executable compiled from the source code representation and represents a plurality of states and possible transitions between states.
17 . The computing system of claim 15 , wherein the software representation comprises a source code representation or an executable compiled from the source code representation and encapsulates a bitmap representing a plurality of states and transitions between states.
18 . The computing system of claim 15 , wherein the software representation represents a plurality of global parameters and access to a plurality of resources depends upon at least respective sets of one or more global parameters of the plurality of global parameters.
19 . The computing system of claim 15 , wherein the system comprises information pertaining to interrelationships between entities.
20 . The computing system of claim 15 , wherein inputs to one or more instances of the software representation are generated by respective fuzzers and a plurality of fuzzers operate in parallel to generate inputs to respective instances of the software representation.