Say we have some complicated function that determines if a string matches an XSS attack string, and throws an error or does something else in that case. ``` function somethingWithXSSVulnerability(x) { var regex = /(.*)/ if (x.match(regex)) { throw new Error('XSS') } else { return x } } ``` In trying to understand symbolic evaluation in regards to test generation, I am wondering how it would generate a test for this case. How it would generate an `x` such that it matched the regex. It could be a lot more complicated than a regex, a grammar for example. The test case generating the error would be something like: ``` // yes case somethingWithXSSVulnerability('alert("foo")') // no case somethingWithXSSVulnerability('anything else even w/o closing tags') ``` To really test it, it might need to generate an alert or try setting a cookie or something, so there it is becoming even more complicated. But I am trying to get a sense of how the symbolic evaluator generates a test for this case. How it determines the value of the input to the function. It seems like it would have to understand the structure of the regex, then reverse-engineer an input to match it. Wondering if that is so.

I have been playing around with analysis of circuits and am trying to generate test vectors. In order to exercise the circuit in the manner I require, I need a vector that includes every change in the circuit's inputs where only 1 input toggles, but in order to be efficient, it must include each change only once and must not include any changes where more than one input toggles. Inputs can be only logic high (1) or low (0). If these sequences don't already have a name I would like to call them Majella tuples. I believe the length of these Majella tuples to be ((2^n) * n) + 1 where n is the width of the input in bits. for example (with all 0 starting patterns): n = 1: 0 1 0 n = 2: 00 10 11 01 11 10 00 01 00 n = 3: 000 100 110 010 110 111 011 001 101 001 011 111 101 111 110 100 101 100 000 010 011 010 000 001 000 I have written a bit of code to brute force generate these codes. However, it starts to struggle at n = 5 (actual code in a prev. revision of this question). ``` FUNCTION gen IF height of stack == ((2^bit_width) * bit_width) PRINT ZERO_PATTERN RETURN TRUE IF the change between the value at the top of stack and value does occur between other values on the stack RETURN FALSE PUSH value to stack WHILE shift < bit_width IF RECURSE with value as (value XOR (1 << shift)) returns TRUE PRINT value RETURN TRUE shift = shift + 1 RETURN FALSE SET stack to an empty list SET bit_width to n CALL gen with value as 0 ``` some properties: I would guess that there are solutions for all every possible n (positive integers). If there is a solution for n, there must be at least n! solutions as swapping the order of the inputs does not invalidate the solution. Reversing the order of a solution also does not invalidate it. In each solution each input pattern should be present n times (except the starting pattern, that is present n + 1 times). The start and end patterns will always be the same. Unfortunately this is wh

My research is mainly focused on generating test sequences automatically using Colored Petri net.CFG provides techniques for generating test sequences. But some papers says that, test sequence generation methods based on a control flow graph sometimes suffers from a feasibility problem (i.e. some paths in a CFG may not be feasible).So I need a technique to draw a Control flow graph from the Colored Petri net model, in a way that, when I will select paths from the control-flow graph it will contain only the feasible paths.Then I will generate test sequences from the CFG. Can anyone help me finding any technique please or give me any suggession??

Let $G$ be a directed graph, with a single source node $s$. I want to find a collection of paths that cover every edge of $G$ (i.e., every edge of $G$ appears in at least one of these paths), where each path must start at $s$. The cost of a collection of paths is the sum of the lengths of the paths. Is there an efficient algorithm to find the minimum-cost collection of paths? This smells like it might be NP-hard to me (it sounds like a set cover problem), so I'm guessing not. If it is NP-hard, are there any good approximation algorithms or heuristics for this problem? This sounds a bit like some kind of network-flow problem. Every collection of paths from $s$ to $t$ is an integral flow from $s$ to $t$, and every integral flow from $s$ to $t$ can be expressed as a union of paths from $s$ to $t$. The difference is that (1) the objective function we are trying to minimize is different from the standard network flow problem, and (2) the starting point of each edge is fixed to $s$, but the ending point is not fixed. So, I don't know if network flow like techniques would help. Motivation: Suppose I have a DFA, and I want to find a testsuite that achieves full edge coverage. A test is a word over the alphabet of the DFA; a testsuite is a collection of tests. A transition is covered by this testsuite if there exists at least one test in the testsuite that causes the DFA to follow that transition at some point. Suppose the cost of a test is its length, and the cost of a testsuite is the sum of the costs of the tests. Then we can ask whether there is an efficient algorithm that, given a DFA as input, outputs a minimum-cost testsuite that achieves full transition coverage. That's exactly the graph problem outlined above.

I have an ordered set of $M$ software modules compiled together. The interaction of some $N$-tuple of these modules is causing a bug when the program is run. I can run the program with any desired subset of the modules enabled/disabled, so I can test the program by running it with a certain subset of modules enabled and seeing whether it crashes or not (call that "a test"). I would like to identify which $N$ modules are causing this issue with the minimal number of tests. Assume that any particular test will lead to a crash if and only if it includes all of the $N$ problematic modules (and possibly others; but at least those $N$). $N$ is known ahead of time. For $N=1$, I can efficiently identify the culprit in $\log_2(M)$ tests by binary search. For other values of $N$, what approach can I take to identify the $N$ culprits?

Considering above terminologies for drawing control flow graphs for any program, it is very simple. For example : ``` While A if B do .. else do .. end while ``` For above example, while doing decomposition, I can say its D2 (D1) i.e while and then inside while, its if-then-else. Considering same situation. How can you represent CONTINUE and BREAK statements Ever for `FOR statement` there is no defined terminology like for `while` and `if then else`. `FOR statement` falls under `while`. My prof says in theory, there is nothing about `Break and continue statement` and I couldnt find anything online too. For example : ``` # include int main(){ float num,average,sum; int i,n; printf("Maximum no. of inputs\n"); scanf("%d",&n); for(i=1;i<=n;++i){ printf("Enter n%d: ",i); scanf("%f",&num); if(num<0.0) break; //for loop breaks if num<0.0 sum=sum+num; } average=sum/(i-1); printf("Average=%.2f",average); return 0; } ``` Control flow graph for this is as below: the nodes has line number written : (Sorry the image is side ways) I decomposed this as : ``` P1;P1;D2(P1;P1;D1);P1 * P1 represents set of statements outside loops ``` I'm not sure if this is correct. My professors says to use something as D22 for break, like create a new term from above image. My main question here is the decomposition. I Know that i drew the CFG correctly, but is the decomposition correct according to the first image?. The break state kind of creates a while as you can see in CFG, but i'm not sure if it has to be considered as while and I guess we cannot, as per my professor. I am working on this and wanted to know, if anyone has come across something for Break and continue statements while decomposition of graphs, please let me know. Thanks. PS : Please, Let me know, if am unclear and if anymore info is needed. I can probably write down an example and upload the picture.

The algorithms for the problem I am working on become more and more complex as I try to improve their performance. They already span several pages with cases and sub-cases, and will probably become even longer. I am worried that there might be mistakes that are difficult to notice. As a programmer, I am used to writing detailed test-cases to test my programs, but the algorithm is written in pseudo-code (it is not easy to implement). What ways can you recommend for testing the algorithm?

This problem arose from software testing. The problem is a bit difficult to explain. I will first give an example, then try to generalize the problem. There are 10 items to be tested, say A to J, and a testing tool that can test 3 items at the same time. Order of items in the testing tool does not matter. Of course, for exhaustive testing, we need $^{10}C_{3}$ combinations of items. The problem is more complex. There is an additional condition that once a pair of items has been tested together, than the same pair does not need to be tested again. For example, once we executed the following three tests: A B C A D E B D F we do not have to execute: A B D because the pair A,B was covered by the first test case, A,D was covered by the second, and B,D was covered by the third. So the problem is, what is the minimum number of test cases that we need to ensure that all pairs are tested? To generalize, if we have n items, s can be tested at the same time, and we need to ensure that all possible t tuples are tested (such that s > t), what is the minimum number of test cases that we need in terms of n, s and t? And finally, what would be a good algorithm to generate the required test cases?

When testing algorithms, a common approach is random testing: generate a significant number of inputs according to some distribution (usually uniform), run the algorithm on them and verify correctness. Modern testing frameworks can generate inputs automatically given the algorithms signature, with some restrictions. If the inputs are numbers, lists or strings, generating such inputs in straight-forward. Trees are harder, but still easy (using stochastic context-free grammars or similar approaches). How can you generate random graphs (efficiently)? Usually, picking graphs uniformly at random is not what you want: they should be connected, or planar, or cycle-free, or fulfill any other property. Rejection sampling seems suboptimal, due to the potentially huge set of undesirable graphs. What are useful distributions to look at? Useful here means that - the graphs are likely to test the algorithm at hand well and - they can be generated effectively and efficiently. I know that there are many models for random graphs, so I'd appreciate some insight into which are best for graph generation in this regard. If "some algorithm" is too general, please use shortest-path finding algorithms as a concrete class of algorithms under test. Graphs for testing should be connected and rather dense (with high probability, or at least in expectation). For testing, the optimal solution would be to create random graphs around a shortest path so we know the desired result (without having to employ another algorithm).