- 论坛徽章:
- 0
|
2.1.4 比较
在原本的计划中,我曾考虑采用常用于字符串相似度比较的编辑距离(Levenshtein Distance)算法[5]。这个算法的含义,是计算两字符串之间的距离有多远。编辑距离是指,从原字符串变化到目的字符串最少需要进行多少次包括添加、修改、删除在内的操作。举例而言:
如果计算kitten和sitting之间的编辑距离,我们最少需要进行3次操作,
1、 kitten -> sitten (修改s->k)
2、 sitten -> sittin (修改i->e)
3、 sittin -> sitting (增加 g)
因此,kitten和sitting之间的编辑距离是3。这个算法是俄国的科学家Vladimir Levenshtein在1965年提出的。这个算法主要是应用在DNA分析、拼字检查、语音辨识和抄袭侦测上。[6]
但是这个算法的计算复杂度太高,是O(nm)的复杂度。对于平均大小在100万行的操作系统内核源代码来说,就是万亿次级别的比对。对于普通的计算机,平均每两个内核的比对就要花去数小时。而此次参与比对的内核将有20个左右,完成一个比较完整的比对过程将会出现几百次比对,那么就要花数个月的时间,不太现实。
因此,这次我采用的是简化的比对办法。通过diff命令来比较两个内核源文件的差异。Diff使用的是一种更聪明的计算方法,虽然最坏情况差不太多,但是大多数情况下具有较高的性能[7]。
通过diff给出的结果可以得知第一个文件增改多少行代码后,就可以变为第二个文件。diff的算法和其实对于修改我们并不介意,我们只关心增加多少行代码就可以变为第二个文件。
假设内核A的代码有a行,内核B的代码有b行。而从内核A变化到内核B需要添加c行,由内核B变化到内核A需要d行。由此,我们可以得知,在内核A中,存在有b-c行代码和内核B是相同的。因此,我们将内核A中所存在的内核B的代码行数除以内核A自身的代码行数定义为两个内核的相似度,即
A->B的相似度 = (b-c) / a
由公式可知,A->B和B->A的计算结果将有可能不同。因为我们判断相似度的原因不单纯是看二者的差异,更重要的是看他们之间的血亲关系的远近,因此我们取双向转换中的最大值,作为A<->B之间的相似度。
A-B间的相似度 = max( (b-c) / a, (a-d) / b )
2.1.5 小结
分析方法还有待完善,可以看出,二进制可执行文件的分析依旧还有很大的难度,很容易受到各种外围环境的变化而导致相似度大幅下降,而无法反映真实的相似度。因此对于那些刻意隐瞒相关性的二进制可执行文件来说还是比较容易的逃过这种分析方法的检测。
但是,分析方法的缺陷却只会导致相似度的下降,而不会导致差异很大的代码产生很高的相似度。因此,我这次采用这次分析方法主要就是确定麒麟操作系统内核与其他操作系统之间的相似度的下限,并从数据中试图分析出他们的血亲关系。
2.2 多种操作系统内核相似度比较
为了比对尽量客观,这次参加比对的操作系统内核包括,FreeBSD, NetBSD, OpenBSD, Linux, Solaris和银河麒麟操作系统,共6个操作系统,22个内核。
原计划中,要将Mac OS X中的Darwin 8.0.1, 7.0.1拿来比对,可是由于其文件格式是Mach-O的,而我又没有支持Mach-O的objdump,所以暂时无法参与比对。另外,原计划曾打算拿相关性更差的Windows NT系列的系统内核来进行比对,可是由于之前所说的PE格式问题而导致的相似度没有参考价值,所以,这次也没有将其列入最终的比对。
为了确认比对的有效性,我们将先对FreeBSD, NetBSD和OpenBSD之间的比对来审视其比对效果。
2.2.1 FreeBSD间不同版本内核相似度分析
FreeBSD是一种Unix衍生操作系统,由BSD, 386BSD和4.4BSD发展而来的Unix的一个重要分支。而BSD的全称是“伯克利软件发布”,是美国伯克利大学计算机系统研究组所制作的一套包括内核在内完整的操作系统,起源于AT&T的Unix V6,但是后来由于与AT&T的版权纠纷问题,彻底的删除了AT&T在BSD内核中的代码,大约占10%左右。也正是这场官司,而给了Linux得以飞速发展的机遇。在版权问题解决后,BSD借助其高质量的代码,在开放源代码的世界里有了飞速的发展,分别产生了3个重要的分支,FreeBSD, OpenBSD, NetBSD。FreeBSD发展至今,已经成为公认的相当可靠和健壮的操作系统。[9,10]
因为焦点集中在FreeBSD身上,而且特别是5.x和6.x的系统上,因此这回参与比较的FreeBSD的内核版本较多,分别有FreeBSD 5.0, 5.1, 5.2, 5.2.1, 5.3, 5.4, 5.5 beta 4和6.0。
原始内核\目标内核 汇编行数 freebsd_5.0 freebsd_5.1 freebsd_5.2 freebsd_5.2.1 freebsd_5.3 freebsd_5.4 freebsd_5.5.b4 freebsd_6.0
freebsd_5.0 913,353 - 697423 712361 714811 969174 1001579 1016967 1146371
freebsd_5.1 958,699 652223 - 682433 681769 1029692 1002484 1034263 1112613
freebsd_5.2 1,048,418 572280 604662 - 3252 817759 865407 850969 1124929
freebsd_5.2.1 1,049,592 493098 607199 2078 - 816434 870479 881654 1124304
freebsd_5.3 1,161,593 742327 762747 705826 724190 - 35581 78219 977778
freebsd_5.4 1,174,287 744511 811979 732332 733290 22906 - 25985 901307
freebsd_5.5.b4 1,187,447 741616 783626 735617 734211 40295 12975 - 358820
freebsd_6.0 1,271,723 791490 805184 905427 907359 753022 766311 622653 -
上表中所列出的是FreeBSD的各个版本之间的差异行数,即前面所说到的c。左边列出的是原始内核,顶端列出的是目的内核。左边给出了原始内核的行数。
差异行数和相似度具有相同的含义,毕竟相似度也是通过差异行数计算出来的,因此在以后的叙述中,我们将只列出相似度对比的表格。
下面就是FreeBSD各个版本之间的内核相似度比较。
原始内核\目的内核 汇编行数 freebsd_5.0 freebsd_5.1 freebsd_5.2 freebsd_5.2.1 freebsd_5.3 freebsd_5.4 freebsd_5.5.b4 freebsd_6.0
freebsd_5.0 913,353 - 28.61% 36.79% 36.65% 21.07% 18.91% 18.67% 13.72%
freebsd_5.1 958,699 27.24% - 38.18% 38.37% 13.76% 17.92% 15.98% 16.60%
freebsd_5.2 1,048,418 32.53% 33.77% - 99.80% 32.80% 29.46% 32.09% 14.00%
freebsd_5.2.1 1,049,592 40.04% 33.49% 99.69% - 32.89% 28.95% 29.13% 14.05%
freebsd_5.3 1,161,593 14.72% 16.87% 29.49% 28.01% - 98.03% 95.49% 25.31%
freebsd_5.4 1,174,287 14.38% 12.49% 26.92% 26.94% 96.97% - 98.91% 31.54%
freebsd_5.5.b4 1,187,447 14.46% 14.74% 26.34% 26.56% 94.43% 97.80% - 76.88%
freebsd_6.0 1,271,723 9.58% 12.07% 11.24% 11.18% 32.13% 32.08% 44.41% -
由于操作系统是逐步发展而来的,因此从5.0-5.5 beta 4都是在前者的基础上,修补前者中出现的bug,并增添新的特性而产生的。我们可以从这个FreeBSD的相似度表中看到这种传承关系。我们可以看出,基本上是越靠近当前版本相似度越高,而离当前版本越远相似度就越低。其中有一些特例的情况,5.1和5.2似乎比较特殊,可能是由于某种原因在5.1中策略有所调整,而在5.2.1或者5.3中又逐渐的恢复回来。
5.2.1和5.2的相似度达到了99.80%,这是正常的,由于在5.2之后,有一系列关键服务,如wu-ftp, OpenSSH和XFree86等的缓冲区溢出的漏洞被揭露出来,致使FreeBSD出于安全考虑而在5.2发布后仅一个月多的时间就立即发布了新的版本,因此5.2.1和5.2的内核上的差异实际上很低,主要是在外围程序上修补了很多安全漏洞[15]。但是出乎我意料的,我没想到在很容易被干扰而降低相似度的情况下,竟然可以达到这么高的相似度,说明这种分析方法对于代码相似度分析在一般情况下是有效的。究其原因,应该是因为FreeBSD的前后传承关系,所以不同的版本虽然代码有不少变动,但是默认的内核配置文件变动不大,因此才有可能出现这种比较高的相似度。另外我们也可以看出,FreeBSD在5.3以后,包括5.4和5.5的内核变动量都不大,由此可以感觉到5.x的系统可能已经基本成熟。
FreeBSD 6.0与5.3以前版本的相似度都不太高,主要是因为6.0已经是和5.x属于不同的代码分支,相对于5.x来说代码有了较大的变化。而另一方面,6.0的分支是在5.4版本发布后建立的,因此,6.0的内核与之前内核的相似度偏低,却和FreeBSD 5.3, 5.4, 5.5 beta 4的相似度较高。
总体上,基本符合版本相近,代码相近的客观事实,分析方法是成功的。
2.2.2 FreeBSD、NetBSD和OpenBSD的内核相似度分析
NetBSD和FreeBSD一样,也是从美国加州伯克利大学的4.3BSD和386BSD衍生出来的Unix操作系统。它以设计简洁、代码规范和高可移植性的特点而著称。从服务器到嵌入式设备都有它的身影[10]。而OpenBSD则是从NetBSD 1.0衍生而来的[11]。因此OpenBSD和NetBSD相对FreeBSD而言具有更近的血亲关系。
原始内核\目标内核 汇编行数 freebsd_5.3 freebsd_6.0 netbsd_2.1 netbsd_3.0 openbsd_3.7 openbsd_3.8
freebsd_5.3 1,161,593 - 25.31% 16.55% 16.61% 16.78% 16.74%
freebsd_6.0 1,271,723 32.13% - 16.65% 16.22% 15.89% 16.24%
netbsd_2.1 1,503,585 13.08% 13.68% - 53.35% 17.53% 16.72%
netbsd_3.0 1,616,659 11.76% 12.65% 24.40% - 13.96% 14.61%
openbsd_3.7 1,228,137 15.60% 16.54% 20.77% 18.44% - 88.89%
openbsd_3.8 1,260,707 15.26% 16.52% 20.65% 18.47% 84.56% -
从这个数据表中,我们可以看出计算出来的数据可以反映这种已知的血亲关系。FreeBSD 与NetBSD和OpenBSD的相似度基本在16.5%左右,而NetBSD与OpenBSD的相似度则相对较高。NetBSD 2.1和OpenBSD的相似度为20.65% ~ 20.77%,NetBSD 3.0和OpenBSD的相似度也有18.44%,都高于FreeBSD与NetBSD和OpenBSD的相似度。虽然数值差别并不大,但是具有规律性,基本上也是客观地反映了真实的情况的。
2.2.3 Kylin与FreeBSD, OpenBSD, NetBSD, Linux, Solaris的内核相似度分析
现在我们开始对银河麒麟操作系统进行相似度比对。参与比对的开放源代码操作系统内核有FreeBSD 5.0, FreeBSD 5.2, FreeBSD 6.0, NetBSD 2.1, NetBSD 3.0, OpenBSD 3.7, OpenBSD 3.8, Linux 2.6.16, OpenSolaris 5.11,共9个内核。
除了刚才介绍过的FreeBSD, NetBSD和OpenBSD外,还增加了Linux和Solaris。Linux是Linus基本上从零起步写出来的操作系统,虽然参考了Minix和Unix的实现,但是基本上没有大量的使用任何其它Unix发布的代码[12]。因此,虽然Linux也是一个类Unix系统,然而由于是独立开发的,所以它和前面所列出的BSD衍生操作系统和后面将要提到的Solaris的血亲关系比较远。
从历史的角度来讲,Solaris和BSD很有渊源。在80年代,Sun基于BSD Unix发布了自己版本的UNIX,SunOS。而在90年代初,由于受到AT&T与BSD的官司影响,Sun将其SunOS 4替换为与AT&T共同开发的UNIX System V Release 4的一个版本,并更名为Solaris 2[13]。在2004年早期,Sun开始了一项计划,名为OpenSolaris,将Solaris逐步的放到开放源代码社区中。并在2005年的6月中旬开放了大部分的Solaris源代码[14]。现在已经有一些基于OpenSolaris源代码的操作系统,这次采用的就是一个名为Belenix的Live CD发布版本0.4.2种的内核,uname显示的是SunOS 5.11。
此次引入Solaris来进行比对,也是从一方面希望能够从分析数据中客观地反映出Solaris,相比Linux而言,和BSD有更近的血亲关系。
关于参与比对的麒麟操作系统内核,我们将从发布版本中获得的四个版本的内核拿来进行比对,Kylin 2.0.0, Kylin 2.0.14, Kylin 2.0.21, Kylin 2.0.21 lsb。需要说明的是,官方网站上发布了2.0.14和2.0.18。其中Kylin 2.0.0是来自于麒麟系统安装盘的引导部分,通过uname –a显示出的版本是2.0.0。Kylin 2.0.21虽然是官方网站给出的光盘镜像的版本号,可是启动后,通过uname –a得到的版本号却是2.0.18,这点可能是麒麟开发组在版本管理上的混乱所导致的。
下面就是分析后得到的数据表;
原始内核\目标内核 汇编行数 fb 5.0 fb 5.2 fb 6.0 k 2-0 k 2-14 k 2-21 k 2-21 lsb l 2.6.16 nb 2.1 nb 3.0 ob 3.7 ob 3.8 os 5.11
freebsd_5.0 913,353 - 36.79% 13.72% 40.53% 30.43% 30.43% 40.53% 6.46% 11.24% 11.37% 10.91% 10.87% 5.02%
freebsd_5.2 1,048,418 32.53% - 14.00% 48.18% 34.02% 34.02% 48.18% 5.75% 11.02% 10.91% 10.95% 10.94% 4.55%
freebsd_6.0 1,271,723 9.58% 11.24% - 12.63% 13.19% 13.14% 12.63% 6.61% 16.65% 16.22% 15.89% 16.24% 5.21%
kylin_2.0.0 1,120,079 31.92% 41.94% 14.55% - 91.06% 91.06% 100.00% 5.38% 10.83% 10.31% 10.20% 10.35% 4.35%
kylin_2.0.14 1,190,443 23.55% 29.98% 24.61% 85.60% - 100.00% 85.60% 5.04% 10.63% 10.64% 10.30% 10.44% 4.06%
kylin_2.0.21 1,190,562 23.52% 29.95% 21.04% 85.57% 99.99% - 85.57% 5.03% 10.72% 10.63% 10.29% 10.44% 4.06%
kylin_2.0.21_lsb 1,120,079 31.92% 41.94% 14.55% 100.00% 91.06% 91.06% - 5.38% 10.83% 10.31% 10.20% 10.35% 4.35%
linux_2.6.16 666,204 9.47% 9.71% 13.13% 5.38% 5.38% 5.39% 5.38% - 11.89% 12.09% 12.21% 12.07% 6.30%
netbsd_2.1 1,503,585 6.49% 7.42% 13.68% 8.06% 8.18% 7.97% 8.06% 5.20% - 53.35% 17.53% 16.72% 4.10%
netbsd_3.0 1,616,659 6.19% 7.11% 12.65% 7.54% 7.90% 7.89% 7.54% 4.98% 24.40% - 13.96% 14.61% 3.73%
openbsd_3.7 1,228,137 7.95% 9.58% 16.54% 9.27% 9.97% 9.71% 9.27% 6.43% 20.77% 18.44% - 88.89% 5.20%
openbsd_3.8 1,260,707 7.72% 8.84% 16.52% 8.88% 9.53% 9.52% 8.88% 6.29% 20.65% 18.47% 84.56% - 5.00%
OpenSolaris_5.11 396,534 11.87% 12.00% 16.84% 12.50% 12.46% 12.46% 12.50% 13.37% 15.90% 15.82% 16.66% 16.49% -
从数据表中反映出来的血亲关系来看,Kylin 2.0的内核和FreeBSD 5.x的血亲关系最近,在30.43%-48.18%之间,和FreeBSD 6.0的关系稍远,在14.55%-24.61%之间。而和其他的操作系统关系都比较疏远。和NetBSD、OpenBSD的相似度在10%左右,而同Linux的相似度只有5.38%,
与OpenSolaris的相似度虽然比NetBSD和OpenBSD还高,达到了12.50%,但是这个绝对数值不应该视为OpenSolaris与麒麟的关系更接近。因为,OpenSolaris的代码行数仅有396,534行,仅相当于NetBSD的1/4。在相似度计算公式中,分母较小,容易致使结果的相似度较大,因此不应该说麒麟内核和Solaris更相似,应该说麒麟内核同Solaris,NetBSD和OpenBSD的相似度相当。
另外,我们可以注意到OpenSolaris和FreeBSD 6, NetBSD, OpenBSD的相似度略高于其他系统内核,但是都比较低。我们从这个不大的差异中可以感觉到Solaris同BSD的或近或远的关系。其实虽然Solaris代码已经不是基于BSD构建的Unix了,但是由于SVR4中也吸收了BSD的部分代码,因此Solaris在相似度上,还是客观的体现了和BSD偏近的关系。
从数据中我们还可以看到麒麟的这几个内核的相似度很高。Kylin 2.0.0和Kylin 2.0.21 lsb的相似度是100%,Kylin 2.0.14和2.0.21的相似度也是接近100.00%。其中的具体差异行数如下:
原始内核\目标内核 汇编行数 kylin_2.0.0 kylin_2.0.14 kylin_2.0.21 kylin_2.0.21_lsb
kylin_2.0.0 1,120,079 - 170,553 170,641 0
kylin_2.0.14 1,190,443 101,029 - 145 101,029
kylin_2.0.21 1,190,562 101,328 26 - 101,328
kylin_2.0.21_lsb 1,120,079 0 170,553 170,641 -
我们可以看出其实光盘引导用的内核同安装后的/boot/kernel_lsb/ 目录下的内核是相同的。而Kylin 2.0.21和2.0.14相比仅仅修改了几十行代码而已,变动很小,从数值上看,变动主要是增加了一些代码。而从2.0.0到2.0.14变动稍大一些。
在后面的分析中,我们没必要对很相似的内核一起进行重复分析,因此,将基于Kylin 2.0.0和Kylin 2.0.21这两个麒麟内核进行分析。
从现在的结果我们已经可以看出麒麟和FreeBSD的5.x版本有很近的血亲关系,最高达到了与FreeBSD 5.2的48.18%的相似度,这种相似性甚至已经明显超过了和FreeBSD具有很近的同源关系的NetBSD, OpenBSD。即使是最初基于NetBSD的代码而建立的OpenBSD,在与其渊源极深的NetBSD比较时,最高也不过20.77%的相似度。
至此,我们基本上可以确定麒麟操作系统内核中有大量的FreeBSD 5.x 的源代码。为了进一步确定麒麟操作系统和FreeBSD的相似性到底有多少,我们接下来将针对Kylin内核和FreeBSD的内核作比较。 |
|