# SPOT: Testing Stream Processing Programs with Symbolic Execution and Stream Synthesizing
## 4 Time Series Stream Synthesis
### Synthesizing Stream Data  
This subsection proposes an approach to synthesize time series streams by assigning temporal relationships to each of the timeless data that we have collected after symbolic analysis.  
Figure 5: Graphic examples for Definitions 4 and 5.  
The synthesis approach works in an iterative process, shown in Figure 6. It mainly consists of the following steps:  
1. By repeatedly solving the contrarians from the symbolic analysis phase, we continuously obtain various stream data. We select \(k\) different data by sampling, and we will set \(k\) larger than the number of paths so that all paths will be covered. The stream data set is expressed as \(\{e_{i}|i=0,...,k-1\}\). Initially, we arrange them in a randomly logical order \(s=[e_{0},e_{1},...,e_{k-1}]\) where \(e_{0}\Leftarrow e_{1}\Leftarrow...\Leftarrow e_{k-1}\).
2. We create a time window in \(L\) length and sample timestamps within this time window. The time window length can be set as the minimum length among all time windows in the DSP program under test. We randomly sample \(k\) timestamps between the beginning (inclusive) of the time window and the end (exclusive) of the time window with uniform distribution.
3. The sampled timestamps are sorted in ascending order and assigned to each data in \(s\) individually according to their logical order. For this stream, the logical order is obedient to the order of timestamps such that it is regarded as the baseline stream that other out-of-order streams will compare with.
4. We begin to generate all possible new reordered streams by altering the order of the baseline stream \(s\) with Algorithm 2 (the algorithm works as an iterative process).
5. We choose one of the new streams, then calculate the RD and entropy for this new stream. If this entropy value is never achieved before, we then choose this stream as one of our potential test suits. Meanwhile, we need to update their timestamps basing on the number of test suites we have already got. Algorithm 3 describes how the timestamps update, and its purpose is to combine all selected streams into one large stream without overlap.
6. We then pick another generated new reordered stream to achieve a new entropy objective.  
Figure 6: The iterative process to generate streams.  
```
Input: List<Tuple2<T, Integer\(>>\) streamList, the baseline stream Output: List<List<Tuple2<T, Integer\(>>\)\(>\) resultList which stores all possible reordering stream init List<Tuple2<T, Integer\(>>\)\(numsList\leftarrow\) new ArrayList() ; foreach\(e\) in streamListdo \(numsList\).add(e) ; end  permute(\(resultList\), \(numsList\), 0) {After execution, \(resultList\) will contain all reordering results} ; Functionpermute(List<List<Tuple2<T, Integer\(>>\)\(>\) resultList, List<Tuple2<T, Integer\(>>\)\(>\)\(numsList\), \(int\)\(num\) if\(num=numsList.size()-1\)then \(resultList\).add(new ArrayList(\(numsList\))) ; end for\(i\gets num\) to\(numsList.size()-1\)do  Collections.swap(\(numsList,num,i\)) ;  permute(\(resultList,numsList,num+1\)) ;  Collections.swap(\(numsList,i,num\)) ;  end
```  
**Algorithm 2**Alter the order of stream and get all possible reordering situations.  
The core of Algorithm 2 is the _permute_ function, which works in a recursive procedure. We have not provided theoretical proof. Instead, we verify its correctness by testing during our developing phase. We design different streams with various lengths from 1 to 5 and feed these streams as input to conduct unit tests. We manually check the results and have observed that the algorithm works as expected.