公开(公告)号：US20060282419A1

公开(公告)日：2006-12-14

申请号：US11140061

申请日：2005-05-28

申请人： Siddhartha Sen ,  Joseph Joy ,  Nikolai Tillmann ,  Colin Campbell ,  Margus Veanes

发明人： Siddhartha Sen ,  Joseph Joy ,  Nikolai Tillmann ,  Colin Campbell ,  Margus Veanes

IPC分类号： G06F17/30

CPC分类号： G06F11/3636 ,  G06F11/3644 ,  Y10S707/99934

摘要： Diagnosing problems in distributed systems. In one aspect, a model of a distributed system defines trace statements are generated by various nodes of the system and placed in log files. The log files are sent to an automatic validator that attempts to reconcile the trace statements against the model. Results of the attempt are indicated. In another aspect, trace statements are received by a multiplexer that creates an ordering via sequence numbers. The ordering is forwarded to an automatic validator to determine whether the trace statements indicate correct behavior.

公开(公告)号：US07548911B2

公开(公告)日：2009-06-16

申请号：US11140061

申请日：2005-05-28

申请人： Siddhartha Sen ,  Joseph M. Joy ,  Nikolai Tillmann ,  Colin L. Campbell ,  Margus Veanes

发明人： Siddhartha Sen ,  Joseph M. Joy ,  Nikolai Tillmann ,  Colin L. Campbell ,  Margus Veanes

IPC分类号： G06F7/00 ,  G06F11/00 ,  G06F9/44

CPC分类号： G06F11/3636 ,  G06F11/3644 ,  Y10S707/99934

摘要： Diagnosing problems in distributed systems. In one aspect, a model of a distributed system defines trace statements are generated by various nodes of the system and placed in log files. The log files are sent to an automatic validator that attempts to reconcile the trace statements against the model. Results of the attempt are indicated. In another aspect, trace statements are received by a multiplexer that creates an ordering via sequence numbers. The ordering is forwarded to an automatic validator to determine whether the trace statements indicate correct behavior.

摘要翻译： 诊断分布式系统中的问题。 在一个方面，分布式系统的模型定义跟踪语句由系统的各个节点生成并放置在日志文件中。 日志文件被发送到一个自动验证器，它尝试将跟踪语句与模型进行协调。 显示尝试的结果。 另一方面，跟踪语句由多路复用器接收，该多路复用器通过序列号产生排序。 排序被转发到自动验证器以确定跟踪语句是否指示正确的行为。

公开(公告)号：US20060212759A1

公开(公告)日：2006-09-21

申请号：US11085624

申请日：2005-03-18

申请人： Colin Campbell ,  Lev Nachmanson ,  Margus Veanes ,  Michael Barnett ,  Nikolai Tillmann ,  Wolfgang Grieskamp ,  Wolfram Schulte

发明人： Colin Campbell ,  Lev Nachmanson ,  Margus Veanes ,  Michael Barnett ,  Nikolai Tillmann ,  Wolfgang Grieskamp ,  Wolfram Schulte

IPC分类号： G06F11/00

CPC分类号： G06F11/36

摘要： Techniques and tools for testing multi-threaded or distributed software systems are described. For example, a multi-threaded system is instrumented and executed to produce logs of events that are performed by each of its agents. The agent logs contain a totally ordered series of events per agent, as well as information about accesses to resources shared between the agents. With this information, a partial ordering of the events performed by all the agents is described for the execution. The agent logs are then multiplexed into one or more serialized event orderings, which can then be compared to a specification of the system in a conformance testing engine.

摘要翻译： 描述了用于测试多线程或分布式软件系统的技术和工具。 例如，多线程系统被检测和执行以产生由其每个代理执行的事件的日志。 代理日志包含每个代理的完全有序的事件序列，以及有关访问代理之间共享的资源的信息。 利用该信息，描述所有代理执行的事件的部分排序用于执行。 代理日志然后被复用到一个或多个序列化的事件顺序中，然后可以将其与在一致性测试引擎中的系统的规范进行比较。

公开(公告)号：US20060242466A1

公开(公告)日：2006-10-26

申请号：US11112282

申请日：2005-04-21

申请人： Nikolai Tillmann ,  Colin Campbell ,  Wolfgang Grieskamp ,  Lev Nachmanson ,  Wolfram Schulte ,  Margus Veanes

发明人： Nikolai Tillmann ,  Colin Campbell ,  Wolfgang Grieskamp ,  Lev Nachmanson ,  Wolfram Schulte ,  Margus Veanes

IPC分类号： G06F11/00

CPC分类号： G06F11/3684

摘要： Techniques and tools for generating test cases for methods or programs with input preconditions are described. For example, after finding feasible control flow paths for a tested method along with each path's associated input conditions, a new program is created which tests these conditions along with the precondition. By analyzing this new program's control flow graph, a class of test cases is found while avoiding inefficiencies created by doing complete searches of paths through the combined control flow graph of the precondition and the method. Additional efficiencies are introduced by partitioning a control flow graph for the precondition into branched and straight sections.

摘要翻译： 描述用于为具有输入前提条件的方法或程序生成测试用例的技术和工具。 例如，在为每个路径的相关输入条件找到可行的控制流路之后，创建一个与前提条件一起测试这些条件的新程序。 通过分析这个新程序的控制流图，发现了一类测试用例，同时避免了通过前提条件和方法的组合控制流程图完成对路径的搜索而产生的低效率。 通过将前提条件的控制流程图划分为分支和直线部分来引入额外的效率。

公开(公告)号：US20060224924A1

公开(公告)日：2006-10-05

申请号：US11097684

申请日：2005-03-31

申请人： Wolfgang Grieskamp ,  Colin Campbell ,  Lev Nachmanson ,  Margus Veanes ,  Michael Barnett ,  Nikolai Tillmann ,  Wolfram Schulte

发明人： Wolfgang Grieskamp ,  Colin Campbell ,  Lev Nachmanson ,  Margus Veanes ,  Michael Barnett ,  Nikolai Tillmann ,  Wolfram Schulte

IPC分类号： G06F11/00

CPC分类号： G06F11/3672

摘要： Techniques and tools for generating finite state machines (“FSMs”) for a software system with asynchronous callbacks are described. For example, method invocations in a model of the software system are partitioned into observable and controlled method invocations. The controlled method invocations are those which can be run from a test harness while the observed method invocations are those which are observed asynchronously as they are invoked in the system. An FSM is created with observation and control nodes such that observable transitions are found from observation nodes and controlled transitions are found from control nodes. If a state of the model contains both controlled and observable invocations, a timeout transition is added to the FSM to give an implementation time to come up with an observed method invocation before continuing to controlled invocations.

公开(公告)号：US20070168927A1

公开(公告)日：2007-07-19

申请号：US11322781

申请日：2005-12-30

申请人： Colin Campbell ,  Margus Veanes ,  Nicolas Kicillof ,  Nikolai Tillmann ,  Wolfgang Grieskamp ,  Wolfram Schulte

发明人： Colin Campbell ,  Margus Veanes ,  Nicolas Kicillof ,  Nikolai Tillmann ,  Wolfgang Grieskamp ,  Wolfram Schulte

IPC分类号： G06F9/44

CPC分类号： G06F8/10 ,  G06F11/3672

摘要： A model composition environment can allow for description of fill or partial symbolic system behavior, as well as the combination of models of specific features into compound models. Compositional operators can include intersection, concatenation, substitution, alternating refinement, as well as a set of regular expression-like operators. Models called “action machines” can represent object-oriented, reactive programs, and an action machine may be composed with another action machine using a compositional operator. This can allow for testing of particular scenarios or behaviors.

摘要翻译： 模型组合环境可以允许对填充或部分符号系统行为的描述，以及将特定特征的模型组合到复合模型中。 组合运算符可以包括交集，连接，替换，交替细化，以及一组正则表达式运算符。 称为“动作机器”的模型可以表示面向对象的，反应性的程序，并且动作机器可以由使用组合操作符的另一动作机构组成。 这可以允许测试特定的场景或行为。

公开(公告)号：US20060179383A1

公开(公告)日：2006-08-10

申请号：US11041087

申请日：2005-01-21

申请人： Andreas Blass ,  Colin Campbell ,  Lev Nachmanson ,  Margus Veanes ,  Michael Barnett ,  Nikolai Tillmann ,  Wolfgang Grieskamp ,  Wolfram Schulte ,  Yuri Gurevich

发明人： Andreas Blass ,  Colin Campbell ,  Lev Nachmanson ,  Margus Veanes ,  Michael Barnett ,  Nikolai Tillmann ,  Wolfgang Grieskamp ,  Wolfram Schulte ,  Yuri Gurevich

IPC分类号： G01R31/28 ,  G06F11/00

CPC分类号： G06F11/263

摘要： State spaces are traversed to produce test cases, or test coverage. Test coverage is a test suite of sequences. Accepting states are defined. Expected costs are assigned to the test graph states. Strategies are created providing transitions to states with lower expected costs. Linear programs and other approximations are discussed for providing expected costs. Strategies are more likely to provide access to an accepting state, based on expected costs. Strategies are used to append transitions to test segments such that the new test segment ends in an accepting state.

公开(公告)号：US20060161404A1

公开(公告)日：2006-07-20

申请号：US11040187

申请日：2005-01-20

申请人： Colin Campbell ,  Lev Nachmanson ,  Margus Veanes ,  Wolfgang Grieskamp ,  Wolfram Schulte ,  Nikolai Tillmann

发明人： Colin Campbell ,  Lev Nachmanson ,  Margus Veanes ,  Wolfgang Grieskamp ,  Wolfram Schulte ,  Nikolai Tillmann

IPC分类号： G06F17/10

CPC分类号： G06F11/3688

摘要： Exploration algorithms are relevant to the industrial practice of generating test cases from an abstract state machine whose runs define the predicted behavior of the software system under test. Here, a new exploration algorithm allows multiple state groupings to simultaneously guide the search for states that are interesting or relevant for testing. In some cases, the algorithm allows exploration to be optimized from exponential to linear complexity. An extended example is included that illustrates the use of the algorithm.

摘要翻译： 探索算法与从运行定义被测软件系统的预测行为的抽象状态机生成测试用例的工业实践相关。 这里，新的探索算法允许多个状态分组同时引导搜索对于测试有趣或相关的状态。 在某些情况下，该算法允许探索从指数线性复杂度进行优化。 包括一个扩展示例，说明了算法的使用。

公开(公告)号：US08515891B2

公开(公告)日：2013-08-20

申请号：US12950586

申请日：2010-11-19

申请人： Margus Veanes ,  Jonathan Paul de Halleux ,  Nikolai Tillmann

发明人： Margus Veanes ,  Jonathan Paul de Halleux ,  Nikolai Tillmann

IPC分类号： G06F17/00 ,  G06N5/02

CPC分类号： G06F11/3684 ,  G06F11/3608

摘要： Described are symbolic finite automata for symbolically expressing and analyzing regular expression constraints, such as for use in program analysis and testing. A regular expression or pattern is transformed into a symbolic finite automaton having transitions that are labeled by formulas that denote sets of characters (rather than individual characters). Also described is composing two or more symbolic finite automata into a resulting symbolic finite automaton that is fully satisfiable. A constraint solver may be used to ensure satisfiability.

摘要翻译： 描述了象征性的有限自动机，用于象征性地表达和分析正则表达式约束，例如用于程序分析和测试。 将正则表达式或模式转换为具有由表示字符集（而不是单个字符）的公式标记的转换的符号有限自动机。 还描述了将两个或更多个符号有限自动机组合成完全可满足的结果符号有限自动机。 可以使用约束求解器来确保可满足性。

公开(公告)号：US07590520B2

公开(公告)日：2009-09-15

申请号：US10758797

申请日：2004-01-15

申请人： Lev Borisovich Nachmanson ,  Margus Veanes ,  Wolfgang Grieskamp ,  Nikolai Tillmann

发明人： Lev Borisovich Nachmanson ,  Margus Veanes ,  Wolfgang Grieskamp ,  Nikolai Tillmann

IPC分类号： G06F9/45 ,  G06F9/44 ,  G06F11/00

CPC分类号： G06F11/3676

摘要： A computerized method creates test coverage for non-deterministic programs. The method receives a graph of edges and states representing a program under test, and creates a continuous cycle of edges that reaches each edge in the graph at least once. In one example, the method splits the continuous cycle into discrete sequences that end at edges reaching non-deterministic nodes in the graph, and verifies that the executing program conforms to the behavior represented by the discrete sequences. In another example, a method creates probabilistic strategies for reaching one or more vertices in a non-deterministic graph. The strategies provide a graph path with a high probability of reaching a desired vertex.

摘要翻译： 计算机化方法为非确定性程序创建测试覆盖。 该方法接收表示正在测试的程序的边和图的图形，并创建一个到图形中每个边缘的连续循环周期至少一次。 在一个示例中，该方法将连续循环分解成在图中到达非确定性节点的边缘处的离散序列，并验证执行程序是否符合由离散序列表示的行为。 在另一示例中，一种方法创建用于在非确定性图中达到一个或多个顶点的概率策略。 该策略提供了具有达到所需顶点的高概率的图形路径。