一个字符串算法库的实现及其形式验证

论文总字数：32305字

摘 要

随着软件在信息社会中发挥日益重要的作用,软件系统的日益复杂，软件规模也越来越大，软件出现错误的可能性及其造成的危害也日益突出，人们对软件可靠性要求也愈来愈高。本课题通过开发一个字符串算法库探讨软件形式化方法的运用。

在算法库开发方面，因为在所有的字符串算法中，字符串匹配算法是其中一个非常重要的课题。在生物信息学，文本处理，互联网浏览器等领域有着广泛的应用。所以本课题主要采用了C 在内的对象式语言实现了bm算法、KMP算法、AC自动机等字符串匹配算法，也尝试运用包括haskell和WhyML在内的函数式语言开发其中部分算法。

在算法库验证方面，在Ubuntu平台配置了 Why3平台，整合了交互式的定理证明辅助工具coq、自动定理证明器CVC3、CVC4等工具对部分算法进行了形式化的验证。验证的算法基于霍尔逻辑和分离逻辑。

关键字：字符串算法，Haskell，霍尔逻辑，分离逻辑，Why3，WhyML

Abstract

As software plays an increasingly important role in the society, software system is becoming increasingly complex. Software errors may cause serious damage. The requirements on software quality are rising. The present study is to investigate the use of formal methods of software by developing a string algorithm library.

In all string algorithms, string matching algorithms are very important for their various applications in such areas as bioinformatics, word processors internet browsers and crawlers. So in this paper some string matching algorithms such as Boyer–Moore algorithm, Knuth–Morris–Pratt algorithm Aho–Corasick string matching algorithm and so on are implemented in C . I also tried to implement some algorithms in Haskell and WhyML.

I configure the why3 platform in Ubuntu to test and verify the algorithm. In this platform, it contains some proof tools such as coq, cvc3, cvc4 and so on. The verification is based on Hoare logic and separation logic.

Keywords: string-algorithm, Haskell, Hoare logic, separation logic, Why3, WhyML

目录

摘 要 I

Abstract II

第一章 绪论 1

1.1 引言 1

1.2 字符串及匹配算法的概述 1

1.3算法验证及其原理 2

第二章 开发环境及相关技术 3

2.1 软件环境 3

2.2 开发技术及平台 3

第三章 算法库的实现(C ) 6

3.1 BF算法 6

3.2 BM算法 6

3.3 KMP算法 9

3.4 AC算法 10

3.5 BNDM算法 14

3.6 Hospool算法 17

3.7算法性能测试与总结 18

第四章 算法实现（Haskell） 20

第五章 霍尔逻辑和分离逻辑 23

5.1霍尔逻辑 23

5.2分离逻辑 26

第六章 Why3平台验证 29

6.1配置验证环境 29

6.2字符串算法的验证 31

结论 40

感谢 41

参考文献 42

第一章 绪论

1.1 引言

随着软件在信息社会中发挥日益重要的作用,人们对软件可靠性要求也愈来愈高.本课题通过开发一个字符串算法库探讨软件形式化方法的运用。

软件形式化并不存在固定的方法，本课题使用不同语言的程序开发和并进行正确性验证。在工作语言的选择上，本课题将主要采用顺序式计算机语言C 实现，也将使用函数式编程语言haskell实现部分算法。

在算法选择方面，本课题选择了字符串匹配算法包括：BF算法、BM算法、KMP算法、AC自动机多模式匹配算法、Horspool算法、BNDM算法。

在验证方面，验证逻辑采用霍尔逻辑，验证平台方面，选用整合了多种验证工具的Why3平台。

1.2 字符串及匹配算法的概述

字符串算法在计算生物学中起着重要作用。字符串或串(String)是由数字、字母、下划线组成的一串字符。一般记为 s=“a1a2···an”(ngt;=0)。它是编程语言中表示文本的数据类型。

字符串算法通常以串的整体作为操作对象，如：在串中查找某个子串、求取一个子串、在串的某个位置上插入一个子串以及删除一个子串等。两个字符串相等的充要条件是：长度相等，并且各个对应位置上的字符都相等。设p、q是两个串，求q在p中首次出现的位置的运算叫做模式匹配。串的两种最基本的存储方式是顺序存储方式和链接存储方式。

在所有的字符串算法中，字符串匹配算法是其中一个非常重要的课题^[1]。它是计算机科学中最古老，也是一个研究最深入的课题之一。字符串匹配的应用也特别广泛，在信息检索，以及生物科学这块，研究尤为重要。在过去的几十年间，字符串匹配算法发展的很快，然而对人们生活而言，非常实用的算法也是近几年才出现。根本原因就在于字符串匹配问题的研究存在理论和应用的脱节。那些专门从事算法研究的学者关心的只是理论上看起来很美妙的算法——具有很好的时间复杂度。而开发人员只是追求实际应用中尽可能快的算法。将理论与实际结合的算法也是近年才出现。

字符串匹配在于从一个文本字符串找到一个或者是所有的关键字词，传统的字符串匹配算法基本分为3块，前缀搜索、后缀搜索、子串搜索。运用包括树、后缀树、后缀数组等数据结构和滑动窗口，位并行，自动机等计算机技术。字符串搜索的代表算法包括BF算法、BM算法、KMP算法、AC自动机多模式匹配算法、Horspool算法、BNDM算法等。

1.3算法验证及其原理

众所周知，随着现代社会的高速发展，软件的概念，软件的使用已经渗透到人们生活的方方面面，在金融行业、航空航天、工作设备的控制，甚至是人们的日常生活都有广泛的应用。软件的错误带来的后果可能是人们难以想象的。1996年6月4日，阿丽亚娜5运载火箭的首飞失败告终。飞行开始只有大约40秒后，在3700米高度，火箭冲出它的飞行轨迹，解体并发生爆炸。总干事欧空局和阿丽亚娜5项目团队的工程师立即开始调查该故障。发生问题的原因在于阿丽亚娜5的航天计算机中的算法程序触发了一个bug，导致了火箭的主处理器是的火箭的运算引擎过载，最终导致火箭解体。而在2000年，由于美国公司所开发的治疗软件错误的计算了对接受放射治疗的病人本应该使用的合适的剂量，最终导致了，巴拿马国家肿瘤中心的肿瘤病人接受了过多的剂量，导致至少8人死亡，超过20名病人的健康受到严重伤害。这样的事，还有很多很多。它们起初源于微不足道的软件错误，带给人和国家的伤害却是严重的。软件的形式验证正是为了避免这些问题^[2]。

传统的软件设计方法一般都是基于自然语言，设计和描述。由于其语义含糊，表达的东西可以带有歧义性，因此，只能依赖于参与者的经验和理解。这种软件设计方法无法做到严格检查，只能依赖与人进行人工分析^[3]。然后就是形式化方法，它就基于严格的定义，有着严谨的数学概念和语言。不同于传统的设计方法，它语义清晰，无歧义。可以利用自动化或者半自动化的工具进行检测和分析。还有一种就是半形式化方法，它语义较清晰，部分内容能被工具检测分析。形式化方法一般分为3部分：（1）形式化规格，采用严格的数学定义和语义，描述软件设计的实现。（2）形式化验证方法，它主要检查设计是否满足一些要求（性能）的过程，主要是相对于传统的验证而言的。（3）精化，从抽象的高层描述触发，推导实现过程中包含的更多细节的规范。反复精华，得到正确可运行的程序。

剩余内容已隐藏，请支付后下载全文，论文总字数：32305字