软件质量工程 08

Nite

0001-01-01

有限状态机 (Finite State Machines, FSMs)

定义与用途

有限状态机 (Finite State Machine, FSM) 是一种用于建模程序执行或行为的中间形式，平衡了表达能力和简单性。
用于描述对象在一段时间内的动态行为 (dynamic behavior)。
元素：
- 状态 (States)：对象的状态集合，代表等待事件或执行活动的时间段。
- 输入 (Inputs)：有限的值集合，通常与状态相关，可能包含条件。
- 转换 (Transitions)：对象在特定状态下对事件的响应，包括：
  - 事件触发 (event trigger)：启动转换的事件。
  - 守卫条件 (guard condition)：布尔表达式。
  - 效果 (effect)：动作。
  - 目标状态 (target state)：转换后的状态。
- 输出 (Outputs)：依赖于状态和输入，与输入条件对应，反映状态的结果。
示例：移动设备的 FSM
- 状态：拨号音 (Dial tone)、拨号中 (Dialling)
- 输入：数字 (digits)
- 转换：每个状态和输入的组合。
- 输出：拨号音 (sound dial tone)，与状态相关。
注意事项：
- 状态的计算可以是任意的，捕获复杂指令的执行。
- 转换遵循正常操作序列。
- 可考虑输入序列的组合或分离。

FSM 表示方法

状态和转换的表示：
- 少量状态：使用图形表示 (graphical representation)，以节点和箭头表示，便于创建。
- 大量状态：使用表格表示 (tabular representation)，记录转换和输出关系，便于工具处理。
- 大量状态、少量转换：使用转换列表 (transition lists)。
- 状态转换表 (State Transition Table)：
  
  当前状态 (Current State) 输入 (Input) 下一状态 (Next State) 输出 (Output)

FSM 局限性

设计变更：FSM 需随设计变更而调整。
潜在问题：状态、转换、输入和输出的不可预见问题。
表示错误：
- 状态错误：
  - 缺失状态 (missing states)：如缺少初始状态。
  - 错误状态 (incorrect states)：如指定错误行为。
  - 多余状态 (extra states)：如输入组合错误。
- 转换错误：
  - 缺失转换 (missing transitions)：如状态序列未连接(unconnected sequence of states)。
  - 错误转换 (incorrect transitions)：如两个状态错误连接(incorrectly connecting two states together)。
  - 多余转换 (extra transitions)：如与产品无关的转换(transitions that do not correspond with the product)。

马尔可夫链 (Markov Chains)

定义与用途

马尔可夫链是带有随机转换 (stochastic transitions) 的 FSM，转换以概率值描述。
表示从时间 $n$ 的状态 $i$ 到时间 $n+1$ 的状态 $j$ 的转换概率 (transition probability)。
每个状态的所有外出转换概率之和为 1。
概率估计：
- 基于应用领域的专家知识 (expert knowledge)。
- 基于历史统计数据 (previously collected statistics)。
- 结合上述两者。
用途：
- 生成状态和转换覆盖 (state and transition coverage)。
- 聚焦于产品最常用的部分。

其他测试方法与工具

复习测试管理工具

任务：作为 PerfectSoftware Pty Ltd 的质量经理，调研支持测试管理 (test management) 的商业工具，优先考虑非主流工具。
评估要点：
- 支持软件需求描述。
- 需求与测试的连接。
- 测试分组(如测试套件)。
- 支持手动测试创建。
- 支持自动化测试创建。
- 支持多测试环境。
- 报告功能。
- 团队协作支持。
- 与项目管理连接(里程碑、期限、交付物、任务创建等)。
- 缺陷跟踪功能或与辅助平台的连接。
- 价格(可能不可用)。

从服务器日志到概率

场景：PerfectSoftware 的网页应用有大量用户，服务器记录每次页面访问的日志。

日志格式：

97.185.220.155
user
-
[09/Oct/2012:17:24:11 +0900]
"GET /platform/folders/user/document.html HTTP/1.1"
401
6012
"https://perfectsoftware.com/platform/folders/user"
"Mozilla/5.0 (Windows NT 6.1; WOW64) AppleWebKit/535.1 (KHTML, like Gecko) Chrome/14.0.835.202 Safari/535.1"

关键字段：
- 字段 5：用户访问的页面。
- 字段 8：包含链接的来源页面。
任务：
- 由于测试所有组合成本过高，需根据功能使用频率分配测试资源。
- 与团队合作，设计处理日志信息并生成概率的流程，将现有 FSM 转换为马尔可夫链。

可能考法与示例考题

可能考法

概念理解：解释 FSM 和马尔可夫链的定义、元素及其在测试中的应用。
应用设计：为特定场景(如移动设备或网页应用)设计 FSM 或马尔可夫链。
错误分析：识别 FSM 中的状态或转换错误并提出修正方法。
工具评估：比较测试管理工具的功能，分析其优缺点。
概率计算：基于服务器日志计算状态转换概率，构建马尔可夫链。

示例考题

问题：简述有限状态机 (FSM) 在软件测试中的作用，并说明其主要元素的构成。(10 分)
- 参考答案(中文)：有限状态机 (FSM) 是一种建模工具，用于描述软件的动态行为，帮助测试人员设计测试用例以覆盖状态和转换。FSM 的主要元素包括：状态(表示对象等待事件或执行活动的时间段)、输入(触发转换的值或条件)、转换(包括事件触发、守卫条件、效果和目标状态)、输出(与状态和输入相关的结果)。
- Reference Answer (English): A Finite State Machine (FSM) is a modeling tool used to describe the dynamic behavior of software, aiding testers in designing test cases to cover states and transitions. The main elements of an FSM include: States (periods where an object waits for events or performs activities), Inputs (values or conditions triggering transitions), Transitions (comprising event triggers, guard conditions, effects, and target states), and Outputs (results associated with states and inputs).
问题：设计一个简单 FSM，用于测试移动设备的拨号功能，包含至少两个状态和两个转换。(15 分)
- 参考答案(中文)：
```
stateDiagram-v2
    [*] --> DialTone
    DialTone --> Dialling : Input digits
    Dialling --> DialTone : Hang up
    note right of DialTone
        Output: Sound dial tone
    end note
    note right of Dialling
        Output: Dialling sound
    end note
```
  说明：FSM 包含两个状态：拨号音 (DialTone) 和 拨号中 (Dialling)。输入“数字 (digits)”触发从 DialTone 到 Dialling 的转换，输出为拨号音；输入“挂断 (hang up)”触发从 Dialling 到 DialTone 的转换，输出为拨号音。
- Reference Answer (English):
```
stateDiagram-v2
    [*] --> DialTone
    DialTone --> Dialling : Input digits
    Dialling --> DialTone : Hang up
    note right of DialTone
        Output: Sound dial tone
    end note
    note right of Dialling
        Output: Dialling sound
    end note
```
  Explanation: The FSM includes two states: DialTone and Dialling. The input “digits” triggers a transition from DialTone to Dialling with the output of a dialling sound; the input “hang up” triggers a transition from Dialling to DialTone with the output of a dial tone.
问题：从服务器日志中提取页面访问数据，如何生成马尔可夫链的转换概率？(10 分)
- 参考答案(中文)：
  1. 提取日志中的字段 5(访问页面)和字段 8(来源页面)。
  2. 统计每对来源页面到目标页面的访问次数，计算从状态 $i$ 到状态 $j$ 的转换频率。
  3. 将频率归一化为概率，确保每个状态的转换概率之和为 1，生成马尔可夫链。
- Reference Answer (English):
  1. Extract Field 5 (accessed page) and Field 8 (referrer page) from the server logs.
  2. Count the frequency of transitions from each source page (state $i$) to target page (state $j$).
  3. Normalize the frequencies into probabilities, ensuring the sum of transition probabilities from each state equals 1, to create a Markov chain.