版权归原作者所有,如有侵权,请联系我们

[科普中国]-执行错误检测

科学百科
原创
科学百科为用户提供权威科普内容,打造知识科普阵地
收藏

简介

在计算机系统中,执行错误检测是指通过执行某种程序检测计算机软件和硬件错误。在实际应用,也有很多领域经常要执行错误检测,例如发音学习系统中。执行错误检测一般都是基于某种算法和策来实现检测错误的意图。

通信中执行错误检测的方法奇偶校验位奇偶校验位(parity bit)是一种非常简单的方案,可以用于检测任何奇数个错误的发生。但如果发生的错误数量为偶数,则奇偶效验位看上去是正确的。对奇偶效验位的扩展和改变有纵向冗余校验、垂直冗余检查,以及双或对角奇偶(在RAID-DP中使用)。

校验和校验码是传送单元中各位的 和,用它可以使接收方检测接收到 的数据是否正确。如果计算结果相 符,可以认为传送过程结束。校验 和是一个固定长度的数据块,它是 作为密码信息中每一位的函数而 产生的;用于校验数据完整性或位 的和。TCP和用户数据报协议 (UDP)通信都使用校验和来检测 传送数据是否正确1。

循环冗余校验(CRC)循环冗余校验(CRC)是一个非安全的散列函数,旨在检测计算机网络中数字数据的意外变化。因此,它不适合检测恶意引入的错误。循环码有着非常适合检测突发错误的有利特性。CRC尤其容易在硬件中实现,兵器因此常用在数字网络和诸如硬盘等存储设备中。奇偶校验是循环冗余校验的特殊案例,其中单比特CRC由除数x + 1生成。

加密散列函数加密散列函数的输出也称消息摘要,它可以提供强力的数据完整性保证,无论数据改变是偶然(例如由于传输错误)还是被恶意引入。对数据的任何修改都可用检测散列值是否匹配判断。此外,指出某些散列值并找到产生相同散列值的另一组输入数据(原输入数据除外)一般是不可行的。如果攻击者不仅能改变消息,还可以改变散列值,那么含密钥散列或或消息认证码(MAC)可用于提供额外的安全性(即密钥散列消息认证码)。在不了解密钥的情况下,攻击者不可能计算出结果正确的含密钥散列值。

错误纠正码纠错码(error correcting code) ,是在接收端能自动地纠正数据传输中所发生差错的码。纠错码的基本思路是在所有的由发送符号组成的序列中,仅挑出其中一部分做为信息的代表向信道发送,并使得所挑出的这些序列之间有尽可能多的差异。每个被挑出的允许发送的序列被称为一个码字,而码字的总合称为码。在发送端把信息变换成码字的过程称为编码;在接收端从接收到的信号判定所发码字、从而恢复信息的过程称为解码(或译码)。在解码时,若收到的信号不是码中的一个码字,则可以肯定在传输中出现了差错,从而着手对差错进行纠正。纠错的方法是找到与接收到的信号最接近的码字,并将其判定为发送信号。一般采用“距离”来度量信号间的接近程度,一种常用的“距离”称为汉明距离,它被定义为两码字间对应位不同的个数总和。一个给定码,其全部码字两两之间距离的最小值被称为这个码的码距。码距是一个码纠错能力的重要参数,例如在汉明距离下,若接收到的信号出错的位数不多于码距的一半,则接收端总能正确地恢复所发送的码字,从而正确地恢复所发送的信息。

纠错编码又称信道编码,它与信源编码是信息传输的两个方面。它们之间存在对偶的关系。应用信道译码直接对一些自然信息进行处理,可以去掉剩余度,以达到压缩数据的目的。

为了使一种码具有检错或纠错能力,必须对原码字增加多余的码元,以扩大码字之间的差别,使一个码字在一定数目内的码元上发生错误时,不致错成另一个码字。准确地说,即把原码字按某种规则变成有一定剩余度的码字,并使每个码字的码元间有一定的关系。关系的建立称为编码。码字到达收端后,用编码时所用的规则去检验。如果没有错误,则原规则一定满足,否则就不满足。由此可以根据编码规则是否满足以判定有无错误。当不能满足时,在可纠能力之内按一定的规则确定错误所在的位置,并予以纠正。纠错并恢复原码字的过程称为译码;码元间的关系为线性时,称为线性码;否则称为非线性码。检错码与其他手段结合使用,可以纠错。检错反馈重发系统(ARQ系统)就是一例。

在构造纠错码时,将输入信息分成k位一组以进行编码。若编出的校验位仅与本组的信息位有关,则称这样的码为分组码。若不仅与本组的k个信息位有关,而且与前若干组的信息位有关,则称为格码。这种码之所以称为格码,是因为用图形分析时它象篱笆或格架。线性格码在运算时为卷积运算,所以叫卷积码。

任何错误纠正码都可用于错误检测。最小汉明距离为d的编码在码字中最多可以检测出d − 1个错误。如果对要检测的最小错误数量有严格限制,使用基于最小距离的纠错码进行错误检测则很合适。最小汉明距离d = 2的编码是纠错码的退化情况,并可用于检测单个错误。奇偶校验位是单错误检测的一个例子。

软件中执行错误检测的方法软件测试为发现软件中的错误而执行程序的过程。软件测试只能用于查找程序中的错误,不能证明程序中没有错误。由于测试的目标是暴露程序中的错误,从心理学角度看,由程序的编写者自己进行全部测试是不恰当的,在综合测试阶段通常由其他人员组成的测试小组来完成测试工作。软件测试是保证软件质量的关键,它是对需求分析、设计和编码的最后复审。因此,软件工程要重视测试。软件测试的方法一般有黑盒测试和白盒测试两种。对于前者已经知道了软件产品应该具有的功能,可通过测试来检验是否每个功能都能正常使用;对于后者,知道软件产品内部工作过程,可以通过测试来检验产品内部动作是否按照规格说明书的规定正常进行。软件测试过程与开发过程类似,必须分步骤进行,每个步骤在逻辑上是前一步骤(若有的话)的继续,也是后一步骤(若有的话)的前提。大型软件系统的测试基本上由模块测试、集成测试和验收测试三个步骤组成2。

静态程序分析静态程序分析(英语:Static program analysis)是指在不运行计算机程序的条件下,进行程序分析的方法。有些程序分析需要在程序运行时才能进行,这种程序分析称为动态程序分析。大部分的静态程序分析的对象是针对特定版本的源代码,也有些静态程序分析的对象是目标代码。静态程序分析一词多半是指配合静态程序分析工具进行的分析,人工进行的分析一般称为程序理解或代码审查。静态程序分析的复杂程度依所使用的工具而异,简单的只考虑个别叙述及宣告的行为,复杂的可以分析程序的完整源代码。不同静态程序分析产生的信息也有所不同,简单的可以是标示可能的代码错误(如lint),复杂的可以是形式化方法,也就是用数学的方式证明程序的某些行为匹配其设计规格。软件度量和反向工程可以视为一种静态程序分析的方式。在实务上,在定义所谓的软件质量指针(software quality objectives)后,软件度量的推导及程序分析常一起进行,在开发嵌入式系统时常会用这种方式进行。