将状态转换系统转换为属性 LTL 公式
Translating a State Transition System to properties LTL formulae
在有界模型检查的上下文中,将系统描述为状态转换系统和需要检查的属性。
当需要向模型检查器工具提供多个系统描述和属性时,手写 属性 会变得乏味。就我而言,我使用了一些时间逻辑。
如何使 translating/parsing 系统描述的过程自动化并从中导出可验证的属性(理想情况下,一组初始状态、转换、状态集)。
例如,考虑给出的微波示例 here 鉴于这样的系统描述,我如何才能有效地得出规范?
据我所知,没有这样的开源工具可以做到这一点。欢迎任何想法、理论方面的方法。
您不能像您建议的那样自动从自动机中导出 LTL 公式,因为自动机比 LTL 公式更具表现力。
这主要给您留下了两个选择:1. 找到一个接受直接表示为自动机的规范的验证工具(我不确定哪些可以,但我怀疑为此检查 SPIN 和 NuSMV 是值得的功能。),或 2. 使用 meta-specification 语言使规范的编写 更容易 ;例如,https://www.isp.uni-luebeck.de/salt (doi: 10.1007/11901433_41) 或 IEE1850/PSL。虽然 PSL 更像是 tool-implementors 的一种语言定义,但 SALT 已经提供了一个网络 front-end,可以将您的输入直接翻译成 LTL。
(顺便说一句,我发现你的方法在方法论上具有挑战性:你不应该从你的模型中推导出公式,而是从你的初始系统描述中推导出公式,因为你要验证的正是这个模型。但我不能 100% 确定,如果我正确理解了你问题中的这一点。)
我认为系统的属性,例如微波系统,来自技术和常识的期望和要求,而不是模型。例如。微波炉应该煮食物。但它不应该开着门做饭。然而,典型 LTL 模式的存储库可用于定义属性。它还列出了属性以及更熟悉的正则表达式和自动机属性。
如果您确定仍要自动将自动机转换为 LTL,请自动检查
https://mathoverflow.net/questions/96963/translate-a-buchi-automaton-to-ltl
堪萨斯规范 属性 存储库
http://patterns.projects.cs.ksu.edu/documentation/patterns.shtml
在有界模型检查的上下文中,将系统描述为状态转换系统和需要检查的属性。
您不能像您建议的那样自动从自动机中导出 LTL 公式,因为自动机比 LTL 公式更具表现力。
这主要给您留下了两个选择:1. 找到一个接受直接表示为自动机的规范的验证工具(我不确定哪些可以,但我怀疑为此检查 SPIN 和 NuSMV 是值得的功能。),或 2. 使用 meta-specification 语言使规范的编写 更容易 ;例如,https://www.isp.uni-luebeck.de/salt (doi: 10.1007/11901433_41) 或 IEE1850/PSL。虽然 PSL 更像是 tool-implementors 的一种语言定义,但 SALT 已经提供了一个网络 front-end,可以将您的输入直接翻译成 LTL。
(顺便说一句,我发现你的方法在方法论上具有挑战性:你不应该从你的模型中推导出公式,而是从你的初始系统描述中推导出公式,因为你要验证的正是这个模型。但我不能 100% 确定,如果我正确理解了你问题中的这一点。)
我认为系统的属性,例如微波系统,来自技术和常识的期望和要求,而不是模型。例如。微波炉应该煮食物。但它不应该开着门做饭。然而,典型 LTL 模式的存储库可用于定义属性。它还列出了属性以及更熟悉的正则表达式和自动机属性。
如果您确定仍要自动将自动机转换为 LTL,请自动检查 https://mathoverflow.net/questions/96963/translate-a-buchi-automaton-to-ltl
堪萨斯规范 属性 存储库 http://patterns.projects.cs.ksu.edu/documentation/patterns.shtml