面试题:求两个各有100亿数据的有序整型数组的交集

by LauCyun Jun 28 15:23:42 2,083 views

最近朋友换工作,遇到这份面试题。

题目:

两个整数数组各有100亿条数据,并已经排序,保存在磁盘上,内存10M。
问:
(1)如何取得交集?时间和空间效率分别是多少?
(2)如果其中一个数组只有100条数据,如何优化算法取得交集?时间和空间效率分别是多少?

 

解题思路:

Q1:

二路归并法:既然两个数组A、B都已经排序,那么扫描一遍两个数组即可。A、B两个数组根据大小移动指针:

  • 如果 A[i]>B[j],则 j++
  • 如果 A[i]<B[j],则 i++
  • 如果 A[i]=B[j],则就是交集数,i++ j++

所以时间效率为\(O(n)\),空辅助空间的复杂度为\(O(1)\)

Q2:

100亿对100亿取交集时,可以借助归并排序的思路,但其中一个是100个元素时,这个问题就退化成了在1亿个有序元素中查找1个元素是否存在的问题。

在这种情况下,可以考虑使用二分查找法。先遍历长度较小的数组,然后将这个元素值在长度较大的数组中进行二分查找。 

所以时间复杂度为\(O(nlogn)\),空辅助空间的复杂度为\(O(1)\)

 

算法实现:

#!/usr/bin/env python
# -*- coding: utf-8 -*-


"""
两个整数数组各有100亿条数据,并已经排序,保存在磁盘上,内存10M。
问:
(1)如何取得交集?时间和空间效率分别是多少?
(2)如果其中一个数组只有100条数据,如何优化算法取得交集?时间和空间效率分别是多少?
"""

import random


class Sort:
    def mergeSort(self, alist):
        if len(alist) <= 1:
            return alist

        mid = int(len(alist) / 2)
        left = self.mergeSort(alist[:mid])
        right = self.mergeSort(alist[mid:])
        return self.mergeSortedlst(left, right)

    # @param A and B: sorted integer lst A and B.
    # @return: A new sorted integer lst
    def mergeSortedlst(self, A, B):
        sortedlst = []
        l = 0
        r = 0
        while l < len(A) and r < len(B):
            if A[l] < B[r]:
                sortedlst.append(A[l])
                l += 1
            else:
                sortedlst.append(B[r])
                r += 1
        sortedlst += A[l:]
        sortedlst += B[r:]

        return sortedlst


def intersection(lst1, lst2):
    """
        Intersection of lst1 and lst2.
    :param lst1: lst1
    :param lst2: lst2
    :return: 
    """
    lst_tmp = []
    i, j = 0, 0
    while i < len(lst1) and j < len(lst2):
        if lst1[i] > lst2[j]:
            j += 1
        elif lst1[i] < lst2[j]:
            i += 1
        else:
            lst_tmp.append(lst1[i])
            i += 1
            j += 1
    return lst_tmp


def binary_search(lst, target):
    """
        Binary search.
    :param lst: lst
    :param target: target value
    :return: index
    """
    if not lst:
        return -1

    start, end = 0, len(lst) - 1
    while start + 1 < end:
        mid = int((start + end) / 2)
        if lst[mid] == target:
            start = mid
        elif lst[mid] < target:
            start = mid
        else:
            end = mid

    if lst[start] == target:
        return start
    if lst[end] == target:
        return end
    return -1


if __name__ == '__main__':
    n = 100
    array1 = [random.randint(0, n) for i in range(n)]
    array1 = Sort().mergeSort(array1)
    array2 = [random.randint(0, n) for i in range(n)]
    array2 = Sort().mergeSort(array2)
    print("array1:", array1)
    print("array2:", array2)
    k = 10
    array3 = [array1[i] for i in range(0, n, int(n / k))]
    print("array3:", array3)


    def q1(lst1, lst2):
        return intersection(lst1, lst2)


    def q2(lst_big, lst_small):
        lst_tmp = []
        small_start, small_end = 0, len(lst_small) - 1
        while small_start <= small_end:
            # 从左边开始二分查找
            index = binary_search(lst_big, lst_small[small_start])
            if (index > -1) and (index < n):
                lst_tmp.append(lst_big[index])
            small_start += 1

            # 从右边开始二分查找
            if small_start < small_end:
                index = binary_search(lst_big, lst_small[small_end])
                if (index > -1) and (index < n):
                    lst_tmp.append(lst_big[index])
                small_end -= 1

        return lst_tmp


    print("Q1(Intersection of array1 and array2): ", q1(array1, array2))
    print("Q2(Intersection of array2 and array3): ", q2(array2, array3))

(全文完)

...

Tags Read More


如何在Windows中安装FFmpeg

by LauCyun Jun 25 20:57:36 633 views

FFmpeg 是一套可以用来记录、转换数字音频、视频,并能将其转化为流的开源计算机程序。它提供了录制、转换以及流化音视频的完整解决方案。它包含了非常先进的音频/视频编解码库 libavcodec。

 

FFmpeg 只有命令行模式,因此安装到 Windows 下时,它与一般安装程序不同,具体安装步骤如下:

第一步:下载 FFmpeg 的 static 版本,根据系统进行选择。下载地址:http://ffmpeg.zeranoe.com/builds/

图1 下载FFmpeg

第二步:解压ffmpeg-20170620-ae6f6d4-win64-static.zip文件,并把文件拷贝到你想存储的地方。我把它放在d:/ffmpeg

图2 存储路径

第三步:设置环境变量

把目录d:/ffmpeg/bin加入到环境变量中,根据你存储的位置适当更改:

图3 bin文件夹

图4 设置环境变量

第四步:检测是否安装成功

打开命令行,执行:

ffmpeg -version

图5 检测是否安装成功

 

输出如图5,则说明安装成功!

 

实战1:使用ffplay播放mp4文件

ffplay test.mp4

图6 ffplay播放mp4文件

 

实战2:把视频转为GIF动态图

ffmpeg -i test.mp4 -vf scale=-1:-1 -t 10 -r 10 test.gif

-i 指定输入文件

图7 视频转为GIF动态图

你可以在FFmpeg支持的各种格式之间进行相互转换。

...

Tags Read More


怎样借助Python爬虫给宝宝起个好名字

by LauCyun Jun 19 19:39:24 8,592 views

每个人一生中都会遇到一件事情,在事情出现之前不会关心,但是事情一旦来临就发现它极其重要,并且需要在很短的时间内做出重大决定,那就是给自己的新生宝宝起个名字。

因为必须在孩子出生一个月内起个名字办理《出生医学证明》,估计很多人都像我一样,刚开始是很慌乱。虽然感觉汉字非常的多随便找个字做名字都行,后来才发现真不是随便的事情,怎么想都发现不合适,于是到处翻词典、网上搜、翻唐诗宋词、诗经、甚至武侠小说,然而想了很久得到的名字,往往却受到家属的意见和反对,比如不顺口、和亲戚重名重音等问题。

于是我们再次回到网上各种搜索,找到很多“男宝宝好听的名字大全”之类的文章,然而这些文章一下子给出几百上千个名字,看的眼花缭乱没法使用。

也有不少的测名字的网站或者APP,输入名字能给出八字或者五格的评分,这样的功能感觉还挺好的能给个参考,然而要么我们需要一个个名字的输入进行测试、要么这些网站或者APP自身的名字很少、要么不能满足我们的需求比如限定字、要么就开始收费,到最后也找不到一个好用的。

于是我想写这么一个程序:

  • 主要的功能是给出批量名字提供参考,这些名字是结合宝宝的生辰八字算出来的;
  • 自己可以扩充名字库,比如网上发现了一批诗经里的好名字,想看看怎么样,添加进去就能用;
  • 可以限定名字的使用字,比如有的家族谱有限定,当前是“嘉”字辈,名字中必须有“嘉”字;
  • 名字列表给出评分,这样倒排后就可以从高分往低分来看名字。

通过这种方式可以得到一份符合自己孩子生辰八字、自己的家谱限制、以及自己喜好的名字列表,并且该列表已经给出了分数用于参考,以此为基准我们可以挨个琢磨找出心仪的名字。当然如果有新的想法,随时可以把新的名字添加到词库里面,进行重新计算。

 

1 程序概述

程序代码结构如下:

F:.
└─baby-name  # 代码根目录
    │  README.md  # README
    │
    └─main   # 代码目录
        │  generate.py  # 主程序及程序入口
        │  __init__.py
        │
        ├─config  # 配置文件目录
        │      sys_config.py   # 程序的系统配置,包含爬取得目标URL、词典文件路径
        │      user_config.py  # 程序的用户配置,包括宝宝的年月日时分性别等设定
        │      __init__.py
        │
        ├─dicts   # 词典文件目录
        │      boys_double.txt   # 词典文件,男孩的多字名字
        │      boys_single.txt   # 词典文件,男孩的单字名字
        │      girls_double.txt  # 词典文件,女孩的多字名字
        │      girls_single.txt  # 词典文件,女孩的单字名字
        │
        ├─outputs # 输出数据目录
        │      example.txt         # 输出的示例文件,内容没有排序
        │      example.txt.sorted  # 输出的示例文件,内容排好了序
        │
        └─scripts # 词典文件预处理脚本
                filter.py
                test.py
                unique_file_lines.py  # 设定词典文件,对词典中的名字去重和去空白行
                __init__.py

使用方法:

  • 如果没有限定字,程序就会使用*_double.txt的词典文件;如果有限定字,程序就会使用*_single.txt的词典文件。您也可以在相应的字典文件里添加词,按行分割添加在最后即可。
  • 打开user_config.py配置文件,配置宝宝的信息。
  • 运行脚本generate.py
  • 运行完成后,在outputs目录中查看结果。

 

2 如何配置

程序的配置如下:

#!/usr/bin/env python
# -*- coding: GB18030 -*-

import os

ROOT_PATH = os.path.join(os.path.dirname(__file__), os.pardir)

setting = {}

# 限定字,如果配置了该值,则会取用单字字典,否则取用多字字典
setting["limit_world"] = "嘉"
# 姓
setting["name_prefix"] = "刘"
# 性别,取值为 男 或者 女
setting["sex"] = "男"
# 省份
setting["area_province"] = "北京"
# 城市
setting["area_region"] = "海淀"
# 出生的公历年份
setting['year'] = "2017"
# 出生的公历月份
setting['month'] = "6"
# 出生的公历日子
setting['day'] = "18"
# 出生的公历小时
setting['hour'] = "18"
# 出生的公历分钟
setting['minute'] = "18"
# 结果产出文件名称
setting['output_fname'] = "example.txt"
setting['output_fpath'] = os.path.abspath(os.path.join(ROOT_PATH, "outputs", setting['output_fname']))

程序根据配置项setting["limit_world"]自动来决定选用单字词典还是多字词典:

  • 如果设置了该项,则程序会组合所有的单字为名字用于计算。比如:设置为“嘉”字,那么嘉滨、嘉濠两个名字都会计算;
  • 如果不设置该项(空字符串),则程序只会读取*_double.txt的双字词典

 

3 程序原理

这是一个简单的爬虫。大家可以打开 http://life.httpcn.com/xingming.asp 网站查看,这是一个POST表单,填写需要的参数,然后点击提交,就会打开一个结果页面,结果页面的最下方包含了八字评分和五格评分等信息。

如果想得到分数,就需要做两件事情:

  • 利用爬虫自动提交表单,获取结果页面;
  • 从结果页面提取分数;

对于第一件事情,很easy,用urllib2即可实现:

# baby-name/main/generate.py, line 94-96

post_data = urllib.urlencode(params)
req = urllib2.urlopen(sys_config.REQUEST_URL, post_data)
content = req.read()

这里的params是个dictionary类型的参数。

params的参数设定如下:

# baby-name/main/generate.py, line 71-92

params = {}

# 日期类型,0表示公历,1表示农历
params['data_type'] = "0"
params['year'] = "%s" % str(user_config.setting["year"])
params['month'] = "%s" % str(user_config.setting["month"])
params['day'] = "%s" % str(user_config.setting["day"])
params['hour'] = "%s" % str(user_config.setting["hour"])
params['minute'] = "%s" % str(user_config.setting["minute"])
params['pid'] = "%s" % str(user_config.setting["area_province"])
params['cid'] = "%s" % str(user_config.setting["area_region"])
# 喜用五行,0表示自动分析,1表示自定喜用神
params['wxxy'] = "0"
params['xing'] = "%s" % (user_config.setting["name_prefix"])
params['ming'] = name_postfix
# 表示女,1表示男
if user_config.setting["sex"] == "男":
    params['sex'] = "1"
else:
    params['sex'] = "0"
params['act'] = "submit"
params['isbz'] = "1"

使用这种方法,就可以提交POST表单,然后从content得到了结果数据。

第二件事情,就是从网页中提取需要的分数,我们可以使用BeautifulSoup4来实现,其语法也很简单:

# baby-name/main/generate.py, line 98-109

soup = BeautifulSoup(content, 'html.parser', from_encoding="GB18030")
full_name = get_full_name(name_postfix)

# print soup.find(string=re.compile(u"姓名五格评分"))
for node in soup.find_all("div", class_="chaxun_b"):
    node_cont = node.get_text()
    if u'姓名五格评分' in node_cont:
        name_wuge = node.find(string=re.compile(u"姓名五格评分"))
        result_data['wuge_score'] = name_wuge.next_sibling.b.get_text()
    if u'姓名八字评分' in node_cont:
        name_wuge = node.find(string=re.compile(u"姓名八字评分"))
        result_data['bazi_score'] = name_wuge.next_sibling.b.get_text()

通过该方法,就能对HTML解析,提取八字和五格的分数。

 

4 程序运行

运行程序后,输出如下:

$ python baby-name/main/generate.py
开始起名................................
1/1287 刘棋嘉	八字评分=90	五格评分=84.8	总分=174.8
2/1287 刘万嘉	八字评分=63	五格评分=73.5	总分=136.5
3/1287 刘嘉荐	八字评分=89	五格评分=86.7	总分=175.7
4/1287 刘嘉飞	八字评分=61	五格评分=81.8	总分=142.8
5/1287 刘崖嘉	八字评分=70	五格评分=75.7	总分=145.7
6/1287 刘嘉纪	八字评分=89	五格评分=81.8	总分=170.8
7/1287 刘嘉菲	八字评分=91	五格评分=74.8	总分=165.8
8/1287 刘嘉纺	八字评分=61	五格评分=86.8	总分=147.8
9/1287 刘早嘉	八字评分=61	五格评分=83.4	总分=144.4
10/1287 刘嘉潘	八字评分=60	五格评分=83.2	总分=143.2
...
1285/1287 刘荧嘉	八字评分=98	五格评分=74.8	总分=172.8
1286/1287 刘炎嘉	八字评分=97.5	五格评分=89.2	总分=186.7
1287/1287 刘嘉宜	八字评分=88.5	五格评分=83.0	总分=171.5
起名完成................................

mian/outputs目录中有两个文件,分别是example.txt.sorted(已排序)、example.txt(没有排序)。

这些分数对于取名还是一个很实用的参考。

 

5 总结

  • 分数跟很多因素有关,比如出生时刻、已经限定的字、限定字的笔画等因素,这些条件决定了有些名字不会分数高,不要受此影响,找出相对分数高的就好;
  • 结果仅供参考,其实历史上很多名人、伟人的姓名八字评分都非常低,但是都建功立业。所以名字确实会有些影响,但有时候朗朗上口就是最好的;
  • 从结果中选取名字之后,可以在百度、微博等地方查查,以防有些负面的人重名、或者起这个名字的人太多了烂大街;
  • 八字分数是中国传承,五格分数是日本人近代发明的,有时候也可以试试西方的星座起名法,并且奇怪的是八字和五个分数不同网站打分相差很大,更说明了这东西只供参考;

本文代码已上传到Github:https://github.com/liuker/baby-name

(全文完)

...

Tags Read More


10 张图详解 TensorFlow 数据读取机制

by LauCyun Jun 08 10:26:02 5,960 views

在学习 TensorFlow 的过程中,有很多小伙伴反映读取数据这一块很难理解。确实这一块官方的教程比较简略,网上也找不到什么合适的学习材料。今天这篇文章就以图片的形式,用最简单的语言,为大家详细解释一下 TensorFlow 的数据读取机制,文章的最后还会给出实战代码以供参考。

 

一、 TensorFlow 读取机制图解

首先需要思考的一个问题是,什么是数据读取?以图像数据为例,读取数据的过程可以用下图来表示:

假设我们的硬盘中有一个图片数据集0001.jpg,0002.jpg,0003.jpg……我们只需要把它们读取到内存中,然后提供给GPU或是CPU进行计算就可以了。这听起来很容易,但事实远没有那么简单。事实上,我们必须要把数据先读入后才能进行计算,假设读入用时0.1s,计算用时0.9s,那么就意味着每过1s,GPU都会有0.1s无事可做,这就大大降低了运算的效率。

如何解决这个问题?方法就是将读入数据和计算分别放在两个线程中,将数据读入内存的一个队列,如下图所示:

读取线程源源不断地将文件系统中的图片读入到一个内存的队列中,而负责计算的是另一个线程,计算需要数据时,直接从内存队列中取就可以了。这样就可以解决GPU因为IO而空闲的问题!

而在 TensorFlow 中,为了方便管理,在内存队列前又添加了一层所谓的文件名队列

为什么要添加这一层文件名队列?我们首先得了解机器学习中的一个概念:epoch。对于一个数据集来讲,运行一个epoch就是将这个数据集中的图片全部计算一遍。如一个数据集中有三张图片A.jpg、B.jpg、C.jpg,那么跑一个epoch就是指对A、B、C三张图片都计算了一遍。两个epoch就是指先对A、B、C各计算一遍,然后再全部计算一遍,也就是说每张图片都计算了两遍。

TensorFlow 使用文件名队列+内存队列双队列的形式读入文件,可以很好地管理epoch。下面我们用图片的形式来说明这个机制的运行方式。如下图,还是以数据集A.jpg, B.jpg, C.jpg为例,假定我们要跑一个epoch,那么我们就在文件名队列中把A、B、C各放入一次,并在之后标注队列结束。

程序运行后,内存队列首先读入A(此时A从文件名队列中出队):

再依次读入B和C:

此时,如果再尝试读入,系统由于检测到了结束,就会自动抛出一个异常(OutOfRange)。外部捕捉到这个异常后就可以结束程序了。这就是 TensorFlow 中读取数据的基本机制。如果我们要跑2个epoch而不是1个epoch,那只要在文件名队列中将A、B、C依次放入两次再标记结束就可以了。

 

二、 TensorFlow 读取数据机制的对应函数

如何在 TensorFlow 中创建上述的两个队列呢?

对于文件名队列,我们使用tf.train.string_input_producer函数。这个函数需要传入一个文件名list,系统会自动将它转为一个文件名队列。

此外tf.train.string_input_producer还有两个重要的参数,一个是num_epochs,它就是我们上文中提到的epoch数。另外一个就是shuffleshuffle是指在一个epoch内文件的顺序是否被打乱。若设置shuffle=False,如下图,每个epoch内,数据还是按照A、B、C的顺序进入文件名队列,这个顺序不会改变:

如果设置shuffle=True,那么在一个epoch内,数据的前后顺序就会被打乱,如下图所示:

TensorFlow 中,内存队列不需要我们自己建立,我们只需要使用reader对象从文件名队列中读取数据就可以了,具体实现可以参考下面的实战代码。

除了tf.train.string_input_producer外,我们还要额外介绍一个函数:tf.train.start_queue_runners。初学者会经常在代码中看到这个函数,但往往很难理解它的用处,在这里,有了上面的铺垫后,我们就可以解释这个函数的作用了。

在我们使用tf.train.string_input_producer创建文件名队列后,整个系统其实还是处于停滞状态的,也就是说,我们文件名并没有真正被加入到队列中(如下图所示)。此时如果我们开始计算,因为内存队列中什么也没有,计算单元就会一直等待,导致整个系统被阻塞。

而使用tf.train.start_queue_runners之后,才会启动填充队列的线程,这时系统就不再停滞;。此后计算单元就可以拿到数据并进行计算,整个程序也就跑起来了,这就是函数tf.train.start_queue_runners的用处。

 

三、实战代码

我们用一个具体的例子感受 TensorFlow 中的数据读取。如图,假设我们在当前文件夹中已经有A.jpg、B.jpg、C.jpg三张图片,我们希望读取这三张图片5个epoch并且把读取的结果重新存到read文件夹中。

对应的代码如下:

# 导入tensorflow
import tensorflow as tf 

# 新建一个Session
with tf.Session() as sess:
    # 我们要读三幅图片A.jpg, B.jpg, C.jpg
    filename = ['A.jpg', 'B.jpg', 'C.jpg']
    # string_input_producer会产生一个文件名队列
    filename_queue = tf.train.string_input_producer(filename, shuffle=False, num_epochs=5)
    # reader从文件名队列中读数据。对应的方法是reader.read
    reader = tf.WholeFileReader()
    key, value = reader.read(filename_queue)
    # tf.train.string_input_producer定义了一个epoch变量,要对它进行初始化
    tf.local_variables_initializer().run()
    # 使用start_queue_runners之后,才会开始填充队列
    threads = tf.train.start_queue_runners(sess=sess)
    i = 0
    while True:
        i += 1
        # 获取图片数据并保存
        image_data = sess.run(value)
        with open('read/test_%d.jpg' % i, 'wb') as f:
            f.write(image_data)

我们这里使用filename_queue = tf.train.string_input_producer(filename, shuffle=False, num_epochs=5)建立了一个会跑5个epoch的文件名队列。并使用reader读取,reader每次读取一张图片并保存。

运行代码后,我们得到就可以看到read文件夹中的图片,正好是按顺序的5个epoch:

如果我们设置filename_queue = tf.train.string_input_producer(filename, shuffle=False, num_epochs=5)中的shuffle=True,那么在每个epoch内图像就会被打乱,如图所示:

我们这里只是用三张图片举例,实际应用中一个数据集肯定不止3张图片,不过涉及到的原理都是共通的。

 

四、总结

这篇文章主要用图解的方式详细介绍了tensorflow读取数据的机制,最后还给出了对应的实战代码,希望能够给大家学习tensorflow带来一些实质性的帮助。

(全文完)

...

Tags Read More


工业控制系统场景指纹及异常检测

by LauCyun Jun 05 23:09:43 4,596 views

工业控制系统(ICS)是监测和控制电力、水务、石油天然气、化工、交通运输、关键制造等国家关键基础设施行业物理过程运行的信息物理系统(CPS)。基于ICS系统中控制通信数据流的持续性和稳定性, 该文提出了从ICS系统工业控制协议交互模式中提取系统级行为特征来作为ICS场景指纹的创新思路和方法。ICS场景指纹不仅能用于识别特定ICS系统, 而且还能用于建立ICS系统正常行为基准并进一步用于识别系统的异常行为。该文构建了采用真实工控设备和软件以及仿真物理过程的实验系统并进行了相关实验验证测试。实验结果表明, ICS场景指纹是ICS系统安全研究方面的一种非常有前景的方法。

工业控制系统(ICS)是数据采集系统(SCADA)、 分布控制系统(DCS)、 可编程逻辑控制器(PLC)等多种类型控制系统的统称[12]。由于工控系统在线长期运行及其安全后果的重要性,工控安全问题日益成为关注重点。近年来震网[3]、 毒区[4]、 火焰[5]等病毒也展示了人们面临的严重信息安全现实威胁。

在传统IT领域中,指纹识别的技术通常采用主动方式,并主要用于渗透性测试、基础设施保护以及辅助入侵检测系统等。正如Caselli等人[6]所讨论的,工业控制系统的设备异构性、专用协议、设备计算能力以及长期运行的TCP会话都使传统设备指纹识别变得更具挑战性。而另一方面,在系统视角上,同传统互联网和IT系统相比,工业控制系统通常展现出规律和可预测的通信模式,它具有长生命周期、稳定的拓扑和规律可预测等行为特性。与IT系统相比,每个工业控制系统都是根据其特定物理过程、使用不同控制设备和软件定制开发的系统,每个工业控制系统在系统层面上更具唯一性。

本文的主要目的是探索建立工业控制系统在系统层面上的指纹,从而为工控系统异常检测、流量分析等运行和安全工作开拓一种新的方向。就作者的知识而言,在这个方向上目前尚未有此类研究。 本文的主要创新包括:

  • 同传统的基于IP和TCP级的流量分析不同,本文认为工控协议级的特性更能反映工控系统物理过程的特性,因此提出基于工控协议级网络流量分析思想;
  • 同采用纯仿真方式缺少真实性以及采用现场流量数据包含大量噪声干扰的方式不同,本文采用了基于场景的混合仿真方式构建了“真实”、“纯净”的工控实验环境,从而能在此环境中更方便地分析反映工控系统物理过程特性的流量特性;
  • 本文提出了基于工控协议双向包长、包到达间隔时间、包方向、包序列向量的工控系统基于场景指纹的系统级特征量,这种特征量更具有泛化性,能更语义地执行工控异常检测,并通过实验验证了其初步有效性。

 

1 相关工作

本文的主要思想源自于工业控制系统同传统IT系统所不同的严格规范性特性(图1)。在这方面,已经有大量综述文献[127]从系统层面上讨论了同传统IT系统相比,工业控制系统具有更长生命周期、更层次化和结构化的体系结构、更稳定的系统拓扑、更低的系统组件变动性等特性。同时,Barbosa等人[8]、 Pleijsier等人[9]实证展示了工业控制系统在网络流量所显示的以高度周期性方式产生流量、有非常稳定的连接图等特性。这些促发了我们寻求工控系统层相对简单、稳定指纹的思考。

图1 工业控制系统典型体系结构图

在传统网络流量分析和指纹辨识方面,Caselli等人[6]提出IT领域中广泛接受的指纹识别技术。Crotti等人[10]的工作,从包大小、到达间隔时间和到达顺序这3种特征出发提出了指纹的概念并用它来实现辨识目的。本文基于这两种方案,提出了新的工控场景指纹概念,建立工控场景模式的行为特征并用于识别工控系统运行中的异常行为。

在工控网络流量分析中,Garitano等人[11]研究建立整体工业控制系统应用网络流量模型的方法,本文则通过真实工业控制软件、硬件以及物理过程的仿真,研究利用网络数据的交互模式来验证特定的工控系统以及异常状态的可行性。在工控系统异常检测方面,Cheung[12]、 Goldenberg[13]和Morris[14]提出针对Modbus协议的入侵检测系统。Barbosa等人[15]使用白名单来描述合法交互。与他们不同的是,本文的研究专注于系统级的流量特征,这是一个工控系统信息安全的新研究方向。

此外,工控系统模型和参考体系结构等为描述和理解工业控制系统提供了公共的框架和术语,是工业控制系统信息安全工作的基础。在工业控制系统领域,ANSI/ISA-99[16]和IEC62443[17]等国际标准给出了5层结构。在本文中,为更好地理解工业控制系统,将工业控制系统简化成过程网络、控制网络和物理过程3部分,参见图1

 

2 实验设置

在工控信息安全研究中,一种方式是使用现实工控系统中采集的网络流量进行分析,它们提供了更现实的复杂环境下的工控研究成果。但这些网络流量包含了各种环境噪声,不能纯净地提供系统在未受干扰和攻击下正常行为特征,而且在真实环境中也无法开展各种攻击和检测流程。另一种情况对工控系统的网际部分,即上位机、 PLC等工控设备,采用仿真方法,虽然它能提供纯净的正常行为,但由于缺少真实网际部分设备,其结果的真实性仍然需要进一步验证。本文聚焦于上位机和PLC等下位机之间的控制系统通信交易这一工控系统最关键的部分,在这方面采用完全真实的软件和硬件构建,而其物理部分采用仿真的物理过程。通过这种方式,确保了工控实验测试床的真实性和有效性,参见图2

图2 工控CSTR场景实验拓扑图

实验场景根据图1所描述的工业控制系统体系结构来构建。该实验场景是建设中的关键基础设施综合实验平台(CPS-based critical infrastructure integrated experiment platform,C2I2EP)的一个组成部分。实验场景包含工控系统和实验分析系统两部分: 实验分析系统用于检测网络流量,执行数据分析任务; 工控系统部分构成如下:

  • 过程网络(上位机): Intouch;
  • 控制网络(PLC): 采用西门子PLC,它同上位机之间通过ISO-over-TCP协议进行通信;
  • 物理过程: 使用Matalab仿真运行CSTR化工模型。

在实验中采用一个标准连续搅拌釜式反应器(CSTR),产生一个一阶不可逆放热反应。过程如图3所示。

图3 CSTR模型

以上物理过程描述如下。

\(dCAdt=qV(CAf−CA)−k0exp(−ERT)CA,\\dTdt=qV(Tf−T)\\−ΔHρCpk0exp(−ERT)CA\\+UAVρCp(Tc−T).\)

 

3 工业控制系统场景指纹

工业控制系统种类繁多,不同的工业控制系统最大的区别在于其所实现的物理过程不同。每一个工控系统(场景)都是一种逻辑和数据的组合[11],工控系统的设计者设计控制逻辑,植入PLC,为监控人员设计HMI系统。最后,HMI和PLC与传感变量和控制变量通过工业控制协议进行交互。通过分析工业控制协议交互行为特征,可以获取工控系统的场景指纹。

接下来对工业控制系统场景指纹进行定义和实验验证。 在本文中,工控系统场景指纹是HMI和PLC之间交易模式的集合,其中交易是通过包时序、包到达间隔时间、包方向、包大小来进行区分的HMI和PLC之间交换的工控协议包的集合。工控场景指纹获取流程如图4所示。

图4 工控系统场景指纹获取流程

步骤1 获取HMI与PLC之间的交互情况。

在步骤1中,可以使用Wireshark等网络流量捕获软件来获取HMI和PLC之间的交互情况,获取的PCAP文件如图5所示。

图5 获取的网络流量PCAP文件

步骤2 协议特征的提取和预处理。

实验采用定义的数据分析工具,如scapy等来提取数据包特征量: 包时序、包大小、包间隔时间和包方向。然后对特征量进行过滤和预处理,最终得到工控协议特征向量集合 \(Pi\)

\(Pi={si,Δti,di},i=1,2,….\)           (1)

其中: 是 HMI⇆⇆PLC 之间交换的第 个包的序号; Δt代表第 个包和前一个包之间的包间隔时间; d代表 HMI⇆⇆PLC 的数据发送方向,即当包属于 HMI→PLC 的流 FHMI 时 d为“+1”,而当包属于 HMI←PLC 流 FPLC 时 d为“-1”。

需要指出的是,在这里已经将包到达间隔时间进行了离散化处理,极大地方便了后续的相关分析工作。

通过对CSTR场景的6 h的运行监控和实验数据分析,初步发现工控协议交互的数据包具有如下特性:

1) 场景中的工控协议中存在长时间的TCP连接,该连接可以持续数个h(可能更长),参见图6。这验证了Caselli等人[6]的观点,并证实了无法使用TCP连接特征来分析工控系统场景。

图6 HMI和PLC之间的TCP长连接

2) 工控协议数据包的包到达间隔时间存在明显的特征,可以用来分辨HMI和PLC之间的交易模式。根据对Δti的观察,存在3种数量级的交互时差: 100ms、 10ms、 1ms。参见表1。

表1 不同数量级的交互时差

序号 包大小 包方向 包向量 间隔时间
1 90 1 90 0ms
2 60 -1 -60 1ms
3 76 -1 -76 20ms
4 60 1 60 200ms
5 133 1 133 100ms
6 60 -1 -60 1ms
7 227 -1 -227 30ms
8 133 1 133 1ms
9 60 -1 -60 1ms
10 90 1 90 10ms

3) 工控协议数据包的包大小 si  和包向量 (si,di) 类型有限,在CSTR场景当中,截取了上百万个数据包也仅存在6类包向量: {(60,+1),(90,+1) ,(133,+1),(60,-1),(76,-1),(227,-1)}。 另外,通过多时间尺度的数据统计,发现几种包向量的数量在不同时间尺度下基本保持不变。参见图7

图7 不同时间尺度下的包向量数量

步骤3 获得工控系统场景交易模式。

通过步骤2的观察,在CSTR场景当中存在交易模式,每一个模式Mj由多个连续特征向量集合组成:

\({{M}_{j}}=\left\{ {{{\dot{P}}}_{0}},{{{\dot{P}}}_{1}},\cdots \right\}.\)                 (2)

获取工控场景交易模式的算法如下所述。

算法1 获取工控场景交易模式
1: input: <Pi={siti,di},I>,
  output: <\({{M}_{j}}=\left\{ {{{\dot{P}}}_{0}},{{{\dot{P}}}_{1}},\cdots \right\}.\) >
2: 通过对场景的分析,发现每个交易都由一个包大小为60的不携带参数的包结束。
3: function Patterns(Pi={siti,di})
4: while(i<I)
5: j=i
6: while(sj !=60)
7: j=j+1
8: if{(si,di),…,(sj,dj)} ¯∈¯M
9: P˙P˙ ={(si,di),…,(sj,dj)}
10: M=M∪{P˙P˙}
11: return M

经算法验证,在CSTR场景当中存在8种交易模式,参见表2和图8

表2 交易模式统计

  交易模式M 数量
M1 {(227,-),(60,+)} 5 021
M2 {(76,-),(60,+)} 47 703
M3 {(90,+),(60,-)} 45 269
M4 {(133,+),(60,-)} 7 475
M5 {(76,-),(90,+),(60,-)} 9 464
M6 {(76,-),(133,+),(60,-)} 13 910
M7 {(227,-),(90,+),(60,-)} 16 366
M8 {(227,-),(133,+),(60,-)} 14 909

图8 CSTR场景交易模式

步骤4 CSTR工控系统场景指纹。

在CSTR场景当中,场景指纹ΦS是交易模式的集合,定义为

ΦS={M1,M2,…,M8}.       (3)

在本次实验中,并未考虑不同的硬件会带来的影响,这将在未来的研究中进一步探讨。

 

4 基于工业控制系统场景指纹的异常检测

4.1 异常检测

通过代表正常系统行为特征的工业控制系统场景指纹,可以有效地检测异常行为。对于新获取的数据流,通过重复步骤1—3获取交易模式并与场景指纹对比,如果出现新的交易模式,就可以判定存在异常行为。下列基于CSTR场景 的异常检测实例可以作为理论研究的例证,在现实的异常检测当中,工业控制系统场景指纹可以作为现有的异常检测手段的一种补充。

4.2 异常检测实验实例

将展示一些实例来验证基于场景指纹的异常检测。在接下来的场景中,假设异常的产生(包括攻击)来自“合法”来源,使用“合法”协议与PLC进行交互。这是工业控制系统当中最难以发现却又最危险的异常情况。

场景1 ISO-on-TCP数据流。

图9中的ISO-on-TCP协议数据流PCAP文件从硬件供应商获得。尽管使用 了相同的协议,但是其中的参数与本文的实验数据并不一致,比如其中包含长度为82的数据包,这在本文的实验场景中从未出现过。

图9 ISO-on-TCP协议数据包

场景2 PLCScan扫描攻击。

图10展示了CSTR实验场景在PLCScan 扫描攻击下的数据流,可以假设攻击者已经拥有了部分权限,可以伪造数据包的参数,比如IP地址、包数据等,以抵抗白名单探测。

图10 PLCScan扫描攻击数据流

但在如图10所示的数据流中,数据包2被伪造成任何大小的数据包都无法匹配已有的场景指纹,这意味着通过基于场景指纹的探测方式可以有效地检测到该攻击的存在。

 

5 结束语

工业控制系统(ICS)信息安全对关键基础设施安全而言是至关重要的。本文认为工业控制系统(ICS)和信息技术(IT)系统之间的最大区别在于:

1) 工业控制系统是信息物理系统,可以直接影响物理世界;

2) 在系统层面,工业控制系统是高度规范性和规律性的生产系统,具有更高的规律性以及稳定性。

通过对仿真实验场景的观察和分析实验,可以获得工业控制系统的系统级特征,本文称为“工业控制系统场景指纹”。这种基于工业控制协议交互行为特征的技术对工业控制系统安全研究是一个有前途的新方向。

本文的研究和实验都只是基于理想模型,其结果暂不适用于真实环境中的复杂模型。 在关键基础设施综合实验平台(C2I2EP)的未来搭建计划中,准备构建更加复杂和真实的实验场景,还会从真实的工业控制系统当中获取数据流来进行进一步研究。另外,在对工业控制系统场景指纹进一步研究时,将扩展工业控制协议数据特征集包括一些TCP/IP底层参数,并使用更有效的数据挖掘方法来对真实的工业控制系统环境下产生的复杂数据进行分析。

 

参考文献

[1] Stouffer K, Falco J, Scarfone K. Guide to Industrial Control Systems (ICS) Security, NIST: special publication 800-82 [R]. 2011.
[2] 彭勇, 江常青, 谢丰, 等. 工业控制系统信息安全研究进展 [J]. 清华大学学报: 自然科学版, 2012, 52(10): 1396-1408. PENG Yong, JIANG Changqing, XIE Feng, et al. Industrial control system cybersecurity research [J]. Journal of Tsinghua University: Sci & Technol, 2012, 52(10): 1396-1408. (in Chinese).
[3] Falliere N, Murchu L O, Chien E. W32.Stuxnet dossier, Symantec white paper [R]. 2010.
[4] Bencsáth B, Pék G, Buttyán L, et al. Duqu: A Stuxnet-like malware found in the wild[R/OL]. (2011-10). http://www.crysys.hu/publications/files/bencsathPBF11duqu.pdf.
[5] sKyWIper Analysis Team. sKyWIper (a.k.a. Flame a.k.a. Flamer): A complex malware for targeted attacks[R/OL]. (2012-05). http://www.crysys.hu/skywiper/skywiper.pdf.
[6] Caselli M, Hadiosmanovi D, Zambon E, et al. On the feasibility of device fingerprinting in industrial control systems [C]//8th International Workshop on Critical Information Infrastructures Security, CRITIS. 2013: 155-166.
[7] Cheminod M, Durante L, Valenzano A. Review of security issues in industrial networks [J]. IEEE Transactions on Industrial Informatics, 2013, 9(1): 277-293.
[8] Barbosa R R R, Sadre R, Pras A. A first look into SCADA network traffic [C]//Proceedings of 2012 IEEE Network Operations and Management Symposium, NOMS. 2012.
[9] Pleijsier E. Towards anomaly detection in SCADA networks using connection patterns [C]//18th Twente Student Conference on IT. 2013.
[10] Crotti M, Dusi M, Gringoli F, et al. Traffic classification through simple statistical fingerprinting [J]. SIGCOMM Comput Commun Rev, 2007, 37(1): 5-16.
[11] Garitano I, Siaterlis C, Genge B, et al. A method to construct network traffic models for process control systems [C]//Proceedings of 2012 IEEE 17th International Conference on Emerging Technologies and Factory Automation, ETFA. 2012.
[12] Cheung S, Dutertre B, Fong M, et al. Using model-based intrusion detection for SCADA networks [C]//SCADA Security Scientific Symposium. 2007.
[13] Goldenberg N, Wool A. Accurate modeling of Modbus/TCP for intrusion detection in SCADA systems [J]. International Journal of Critical Infrastructure Protection, 2013, 6(2): 63-75.
[14] Morris T, Vaughn R, Dandass Y. A Retrofit network intrusion detection system for MODBUS RTU and ASCII industrial control systems [C]//Proceedings of the 2012 45th Hawaii International Conference on System Sciences. 2012.
[15] Barbosa R R R, Sadre R, Pras A. Flow whitelisting in SCADA networks [J]. International Journal of Critical Infrastructure Protection, 2013, 6(3-4): 150-158.
[16] ANSI/ISA-99.01.01-2007. Security for industrial automation and control systems: Terminology, concepts and models [R]. 2007.
[17] IEC/TS 62443-1. Industrial communication networks- Network and system security-Part 1-1: Terminology, concepts and models [R]. 2009.

 

本文转载于彭勇, 向憧, 张淼, 陈冬青, 高海辉, 谢丰, 戴忠华. 工业控制系统场景指纹及异常检测[J]. 清华大学学报(自然科学版), 2016, 56(1): 14-21

(全文完)

...

Tags Read More