有关状态机编译器的帮助 [英] Help on State Machine Compiler

问题描述

大家好，

我正在从事软件测试，特别是自动测试用例生成。在现有的测试用例中，我的重点是由事件序列组成的测试用例，例如_.event1.event2 ... eventx（）



但是，事件可分为：敏感和不敏感。后者不会影响系统的状态，因此可以忽略;而前者会影响各州。无论如何，测试案例中的敏感事件可能导致国家爆炸，并且需要防止这种情况发生。因此，一些技术建议使用一个变量来呈现状态并将所有相似的状态组合在一起，例如在循环队列中使用len变量。相对而言，状态可以通过使用特定图纸来表示，例如FSM。



例如，循环队列的测试用例可能如下所示：



add（0）.remove（）。add（1）.Front（）

add（0）.add（1）.remove（）。Front（ ）



产生以下状态：

Hello everybody,
I ‘am working in software testing, specifically automatic test cases generation. Among the existing forms of test cases, my focus is on the test cases that are composed of sequences of events such as _.event1.event2…eventx()

However, the events can be classified into: sensitive and insensitive. The latter does not affect the system’s states, and hence, it can be ignored; while the former affects the states. Anyhow, the sensitive events in the test cases may lead to states explosion and there is a need to prevent that. Therefore, some techniques suggest using one variable to present states and group all similar states together such as using len variable in circular queue. Relatively, the states can be represented by using specific drawings such FSM.

For example, the test cases for circular queue may look like:

add(0).remove().add(1).Front()
add(0).add(1).remove().Front()

which produce the following states:

len=1, rear=0, front=0 and dataQ[0]=0
len=0, rear=0, front=1 and dataQ={0}
len=1, rear=1, front=1 and dataQ[1]=1
len=1, rear=0, front=0 and dataQ[0]=0
len=2, rear=1, front=0 and dataQ[1]=1
len=1, rear=1, front=1 and dataQ={1,0}

可以看出，每次添加/删除都会产生一个新状态。状态由4个变量组成：len，rear，front和dataQ。前三个变量是整数，而dataQ是整数数组。尽管如此，不同测试用例产生的状态可能相同，这会浪费精力和时间。因此，需要优化这些状态。提出了搜索技术，其中问题可以表示为搜索问题并且应用该技术。如果我们将Len视为一个州，那么我们将得到：len = 0; 0QSize。但是，这并不代表州，但它适合将州分为几组。



在状态表示方面，建议使用状态机/地图编译器（SMC）作为一种建模机制，它采用状态机（即FSM）绘制并以任何首选语言生成代码。在SMC中，FSM以特定语法（状态---转换----下一状态）表示并保存在文件（.sm）中。此文件将由SMC编译以生成上下文类，该上下文类包括FSM中的状态，转换和操作的定义，但仍需要由另一个类触发。这个类必须调用修改状态的转换。



我们已经创建了该类并使用它们的转换实现了所有方法。但是，使用的FSM仅基于1个变量（即len）。此外，我们仍在寻找SMC结果，因为它们将成为任何搜索技术的输入。据推测，SMC生成的状态可以直接用于搜索技术，但这仍然值得怀疑。好的，我们需要你的帮助。



关心

As can be seen, every addition/deletion produces a new state. A state is composed of 4 variables: len, rear, front and dataQ. The 1st three variables are integers while the dataQ is an integer array. Nonetheless, the states produced by different test cases can be identical which wastes effort and time. So, there is a need to optimize these states. The search techniques were suggested where the problem can be represented as a search problem and the technique is applied. If we consider Len as a state, then we will have: len=0; 0QSize. However, this does not represent the state but it suits for classifying the states into groups.

In terms of states representation, State Machine/Map Compiler (SMC) was suggested as a modeling mechanism that takes the state machines (i.e. FSM) drawing and generates the code in any preferred language. In SMC, the FSM is represented in a specific syntax (state---transition----next state) and saved in a file (.sm). This file will be compiled by SMC to generate a context class which includes definitions of states, transitions and actions in FSM but still need to be triggered by another class. This class has to call the transitions that modifies the state.

We had created that class and implemented all the methods with their transitions. However, the FSM used was based on 1 variable only (i.e. len). Besides, we are still looking for the SMC results as they will be the input for any search technique to be applied. Supposedly, the states generated by SMC can be used directly in the search technique but this is still questionable. Kindly, we need your help with this matter.

Regards

推荐答案

很抱歉没有给你一个积极的回答。答案必须是否定的，因为你刚刚证明进入FSM方法荒谬的领域，以及不可测试算法的领域。



是，许多算法根据定义是不可测试的，并且许多算法都在测试 - 不可行。对于一些不可能进行测试的算法，一些随机测试可能有意义，但不适用于所有这些算法;而且，无论如何，没有可行的详尽测试。举一个明显的不可测试算法的例子，考虑测试一些加密算法是否加密强度的问题。当然，如果您知道该算法存在缺陷，理论上可能只能找到一个计算可行的反例来证明该缺陷。但是没有找到这样的反例，这是不可行的，只是因为算法的目标是使逆向操作不可行。当然，存在加密算法的测试项目，但结果只能在算法被成功破解的情况下用作证明。还有一些原则上无法测试的算法。



但为什么我认为你会遇到这种情况呢？首先，让我们考虑FSM方法。 FSM方法真正面向详尽的测试。 FSM不是基于变量。它基于状态集，并且该组转换可以被理解为该组状态的笛卡尔平方的子集。但实际上，它应该是这个子集的一个函数。笛卡尔平方的所有元素（可能不仅仅是它的子集）可能带有一些有用的信息;例如，表示无效转换的单元格可能带有解释禁止转换原因的信息（例如，当锁未打开时，您不应将门移动到打开位置，当检测到操作员的手时，您不应关闭门机器）。类似的东西。



现在，考虑一些长度值的集合。如果使用浮点值（例如double），FSM的荒谬性将变得尤为明显。显然，你有2个值（其中一些在语义上是相同的，例如NaN的不同表示，但它不会改变图片）。笛卡尔方形将具有2⁶⁴*2⁶⁴个单元格。如果这还不够，考虑更真实的情况，当用x，y，z，θ坐标描述状态时。不够？它可以很容易地达到100度的自由度。我将留下您的家庭练习来计算这种FSM中的状态数量以及测试的可行性。但问题甚至不是状态的数量，这个想法是原则：即使浮点值集合形式上是有限集合，这种数据类型的想法是表示实数的集合，精度有限。该模型是有限的，但建模对象不仅是无限集，它也是一个连续体（你明白差异吗？你需要）。这使得测试本身的标准非常模糊。这就是为什么许多浮点算法不仅不能用于测试，而且原则上不可测试。



但是基于纯整数状态值的模型会改善这种情况吗？是的，它可以，但它不会消除可行性问题。我可以自己解决。



请参阅：

http://en.wikipedia.org/wiki/Test_data_generation#Infeasible_Paths [ ^ ]，

http：/ /en.wikipedia.org/wiki/Test_plan [ ^ ]，

http://en.wikipedia.org/wiki/Test_data [< a href =http://en.wikipedia.org/wiki/Test_datatarget =_ blanktitle =New Window> ^ ]，

http://en.wikipedia.org/wiki/Software_testing [ ^ ]。



所以，尽管如此我没有给你一个解决方案，我希望我的帖子可以帮你节省时间，而不是撞墙砖。您可以改为采用一些随机测试方法。

-SA

Sorry for not giving you a positive answer. The answer has to be negative, because you just demonstrated entering such domain where the FSM approach would be absurd, and also the domain of the non-testable algorithms.

Yes, many algorithms are not testable by definition, and many are testing-infeasible. For some of such algorithms infeasible for testing, some stochastic testing may make sense, but not for all of them; and, anyway, there is no feasible exhaustive testing. To give one obvious example of non-testable algorithm, consider the problem of testing if some cryptographic algorithm is cryptographically strong or not. Of course, if you know that the algorithm has the flaw, it could be theoretically possible to find out just one counter-example which is computationally feasible to demonstrate the flaw. But it such counter-example is not found, it is infeasible, just because the goal of the algorithm is to make reverse operation infeasible. Of course, the projects of testing of the cryptographic algorithms exist, but the result can be used as a proof only in the case when algorithm is successfully broken. And there are the algorithms which are not testable in principle.

But why do I think you are coming to this situation? First of all, let's consider FSM approach. FSM approach is really oriented to exhaustive testing. FSM is not "based on a variable". It is based on the set of states, and the set of transitions can be understood as the subset of Cartesian square of the set of states. But in practice, it should rather be a function over this subset. All the elements of the Cartesian square (maybe not only its subset) may carry some useful information; for example, the cell representing invalid transition may carry information explaining the reason for prohibiting the transition (for example, you should not move the door into open position when the lock is not open, you should not close the door when operator's hand is detected inside the machine). Something like that.

Now, consider the set of some Length values. The absurdity of FSM becomes especially apparent if you use floating-point value, such as double. Apparently, you have 2⁶⁴ values (some of them are semantically identical, such as different representations of NaN, but it does not change the picture). The Cartesian square will have 2⁶⁴*2⁶⁴ cells. If this is not enough, consider more realistic case, when the state is described with x, y, z, θ coordinates. Not enough? It could be easily some 100 degrees of freedom. I'll leave for your home exercise to calculate the number of states in such a FSM and the feasibility of testing. But the problem is not even the number of states, the idea is the principle: even though the set of floating-point values is formally a finite set, the idea of such data type is to represent the set of real numbers, with some limited accuracy. That model is finite, but modeled object is not only infinite set, it is also a continuum (do you understand the difference? you need to). That makes the criteria of testing itself quite fuzzy. That's why many floating-point algorithms are not only infeasible for testing, but not testable in principle.

But will the model based on purely integer state values improve the situation? Yes, it can, but it won't remove the feasibility problem. I you can figure it out by yourself.

Please see also:
http://en.wikipedia.org/wiki/Test_data_generation#Infeasible_Paths[^],
http://en.wikipedia.org/wiki/Test_plan[^],
http://en.wikipedia.org/wiki/Test_data[^],
http://en.wikipedia.org/wiki/Software_testing[^].

So, even though I did not offer you a solution, I hope my post will help you to save time by not ramming the brick wall. You can address some stochastic testing approaches instead.

—SA

这篇关于有关状态机编译器的帮助的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！