基于机器学习的密码强度评测微服务实现
1.K-最近邻算法
距离计算数学描述：
对于任意的特征向量x:
ar(x)表示实例x的第r个属性值，两个实例xi和xj之间的距离定义为d(xixj)
根据欧式距离公式：
训练算法：
对于每个训练实例
分类算法：
给定一个要分类的查询实例xq，在训练实例列表中选出最邻近xq的k个实例，并用x1…xk来表示，定义离散目标函数
V是有限集合{v1，v2...vs}，则
其中如果a=b那么
否则
对前面的K最近邻算法做一下简单修改，使其能被用于逼近连续值的目标函数，为了达到此目标，我们只需要让算法计算K个最临近实例的平均值，而不再是计算其中的最普遍的值，定义实值目标函数
则
2.决策树
决策树(DecisionTree)，顾名思义，是一种树——依托策略抉择而建立的树。在机器学习里面，它是一个预测模型，它所代表的是一个对象的属性和值之间的映射关系。决策树是应用最广的归纳推理算法之一，属于监督学习中的一种，所谓监督学习，就是给定一定数量的都有属于自己的一些属性以及类别的样本。其中类别是根据数据本身属性确定的，然后，通过对样本数据进行训练学习得到一个分类器，得到的分类器可以对新出现的实例进行分类，这种机器学习方式就被称为监督学习。
我们可以用下面的箭线图1-1来形象的表示决策的过程的各个阶段之间的联系。
图1-1决策树决策过程关系图
选择分割的方法可以有很多，但最终目的一致：也就是对目标类尝试进行最佳分割，由于从根到叶子有多条路径，一条规则对应一条路径，很明显，决策树是一颗二叉树或多叉树。
决策树有四种构成要素，决策结点、状态节点、方案枝、概率枝。决策结点也叫方块结点；状态结点又叫圆形结点；决策结点引出若干条分支每条分支代表一个方案，故称方案枝；状态结点又会引出很多分支，代表不同的状态，由于上面会反映客观状态和出现的频率，每个分支又被称为概率枝，在概率枝的末端会有该状态下所达到结果也就是权重值。如图1-2所示。
图1-2决策树图标示例
3.训练数据准备
4.数据预处理
密码按长度和字符类型划分为五个维度，分别是密码长度，是否含有数字，是否含有大写字母，是否含有小写字母，是否含有特殊字符。程序简单实现如图1-3所示。
图1-3数据预处理python主要代码
5.算法实现5.1K最近邻算法密码评测
对未知密码强度密码实施KNN分类算法伪代码如下：
1）计算已知密码强度数据计算密码强度向量与当前密码向量之间的距离
2）对上一步计算结果按照距离递减排序
3）选出与当前密码向量距离最小的TopK个密码向量，K为20
4）确定TopK个向量所在类别占数据集或抽样数据集密码强度的比例
5）返回TopK个向量比例最高的密码强度为当前密码向量密码强度
经过数据打散，抽样，并按等同比例获取四种密码强度数据，用Matplotlib画散点图如图1-4所示，从图中密码强度分布中，大致可以看出符号种类越多越强，密码位数越多越强的规律。
图1-4KNN数据建模呈现图
5.2决策树算法密码强度评测
对未知密码强度密码实施决策树分类算法伪代码如下：
1）创建唯一的影响密码强度分类的因素列表
2）计算每种划分方式下密码强度数据的香农熵
3）找出最好的信息增益计算方式
4）因为特征值有多个，一次划分后可以再次划分数据，需要递归划分数据
5）存储训练数据得到的树，并能够解析决策树，以供新密码向量遍历
6）比较当前密码向量的与树节点的值，如果到达叶子节点，返回这个叶子节点的密码强度分类。
经过数据打散，抽样，并按等同比例获取四种密码强度数据，通过上述算法实现后得到如下决策树：
{'密码字符种类':{1:{'密码长度':{8:弱,9:一般,:一般,11:一般,12:弱,13:弱,14:一般,15:弱,16:一般}},2:{'密码长度':{8:弱,9:弱,:一般,11:较强,12:一般,13:一般,14:一般,15:强,16:一般}},3:{'密码长度':{8:一般,9:较强,:较强,11:强,12:较强,13:强,14:强,15:强,16:强}},4:{'密码长度':{8:强,9:较强,:强,11:较强,12:强,13:强,14:强,15:强,16:强}}}
图1-5密码强度决策树
环境搭建，测试实验
搭建Kubernetes的方式有很多，在研究过程中，经过从最初的在本地虚拟机原生搭建1.6，在阿里云服务器上用Kubeadm搭建1.8，本地虚拟机Kubeadm搭建1.10，本地Vagrant搭建1.11，谷歌云服务器KubernetsEngine直接搭建1.12等实验。发现本地原生搭建是最麻烦的，因为集群搭建过程中需要通过自创建各种证书，一步步的安装各个组件和启动各个节点，较繁琐。谷歌云直接用Kubnernets引擎搭建是最迅捷的，只需要选择需要版本就可以。综合考虑研究部分步骤的必要性及通用性价值，最终选择在阿里云服务器采用Kubeadm搭建，Kubeadm是官方提供的自动化安装工具，自动配置了必要的服务和安全的认证，主要组件都变成Pod而非操作系统进程，这样可以不断检测其状态并且进行相应的容错处理，本章主要内容就是借助Kubeadm搭建高可用Kuberntes集群，并讲述了在部分核心资源不可获取时如何应对[10]。
1.Docker及Docker-Registry搭建
1.1安装Docker
Docker安装相对Etcd比较简单，可以选择如下三种方式之一：
1）通过配置软件源安装：
官方源：
为了确认所下载软件包的合法性，需要添加软件源的GPG密钥，命令参考如下：
然后，我们需要向source.list中添加DockerCE软件源：
国内源：
然后执行更新安装
apt-getupdateapt-getinstalldocker-ce
2）脚本安装：
Docker官方为了简化安装流程，提供了一套便捷的安装脚本
curl-fsSLget.docker.com-oget-docker.shshget-docker.sh--mirrorAliyun
执行此命令后，脚本就会自动将一切准备工作做好，并把DockerCE的Edge版本安装在系统中。
3）二进制安装：
配置/etc/systemd/system/docker.service：
启动：
systemctlenabledockersystemctlstartdocker
1.2Docker-Registry搭建
有了Docker，搭建Docker-Registry就更简单了，借助于Registry镜像，可以用如下命令一键搭建：
dockerrun-d\\-p5000:5000\\-v/opt/registry/data:/var/lib/registry\\--restart=always\\--nameregistry\\registry
这里需要注意的是，搭建好Kubernetes后需要添加本地指定的Docker-registry，使用如下命令，不然默认是连接docker.hub。
kubectlcreatesecretdocker-registry--docker-server=localtest.registry.com:9000--docker-username=username--docker-password=password--docker-email=username@xxmail.com
2.Etcd集群搭建
2.1二进制模式安装
下载二进制文件，解压，然后拷贝到指定目录，命令参考如图2-1。
图2-2Etcd二进制安装命令
图2-3Etcd集群状态信息
2.2Docker模式搭建
Docker方式跟二进制方式大同小异，只是每个ectd节点运行在一个docker容器中，具体命令如图2-4所示。
图2-4Docker搭建Etcd命令（1）
图2-4Docker搭建Etcd命令（2）
3.Kubernetes集群搭建
3.1安装Kubeadm、Kubelet、Kubectl
网络正常及有正常可用apt源的时候很简单，就是简单的如下更新安装：apt-getupdate&&apt-getinstallKubeadmKubeletKubectl，这里额外介绍一种在研究初期无安装源及无可用命令行翻墙配置时的方式。
1）翻墙下载packages索引
这里选择1.8版本，具体索引如下：
2）根据Filename下载对应的deb
3）构建本地软件源并更新安装
dpkg-scanpackages./|gzip->./Packages.gzapt-getupdateapt-getinstallKubeadmapt-getinstallKubeletapt-getinstallKubectl
4）配置kubeadminit的配置文件
图2-5Kubeadm初始化时Kube-config.yaml配置文件
3.2Kubeadm初始化
FROMgcr.io/google_containers/kube-scheduler-amd64:v1.6.0，具体Dockerhub配置如图2-6所示。
图2-6Dockerhub配置Github自动构建图
之后通过命令拉取下来重新打一下标签就行：
dockerpullraysail/Kube-scheduler-amd64:v1.8.0dockertagraysail/Kube-scheduler-amd64:v1.8.0gcr.io/google_containers/Kube-scheduler-amd64:v1.8.0
需要转存的镜像镜像列表如下：
gcr.io/google_containers/Kube-scheduler-amd64:v1.8.0gcr.io/google_containers/Kube-apiServer-amd64:v1.8.0gcr.io/google_containers/Kube-controller-manager-amd64:v1.8.0gcr.io/google_containers/Kube-proxy-amd64:v1.8.0gcr.io/google_containers/k8s-dns-Kube-dns-amd64:1.14.5gcr.io/google_containers/k8s-dns-dnsmasq-nanny-amd64:1.14.5gcr.io/google_containers/k8s-dns-sidecar-amd64:1.14.5
另外，为了使Flannel正常工作，Kubernetes官方文档指出，在Kubeadminit时候必须要追加--pod-network-cidr=10.244.0.0/16参数[10]。因为上面在引入外部高可用Etcd集群时已经采用了Kubeadm的配置文件方式，且Flannel的CIDR配置参数不能用--config同时存在，所以需要在Kube-config.yaml文件中增加如下两行配置:
networking:podSubnet:10.244.0.0/16
Kubeadm初始化成功后，可以用命令检查组件状态
kubectlgetcomponentstatuses，执行结果如图2-7所示。
图2-7Kubernetes集群初始化后组件健康信息
3.3安装Flannel
因为已经安装了Kubectl，Flannel可以直接用Kubernetes的形式安装，命令如下:
3.4加入Nodes
Kubeadm初始化后会生成一个token，用此token通过命令:kubeadmjoin--token86d22a.123582ce916b31fc10.0.30.104:6443加入节点，分别在Master之外的两台机器执行上述命令后，Kubelet会分别在两台Node上启动Flannel和Kube-proxy，如图2-8所示。
图2-8Kuberntes集群搭建完成pod示例图
4.密码评测微服务搭建部署
4.1构建服务镜像
因为两个基于机器学习的密码强度评测算法都是用Python实现的，而其中因为涉及到很多数组或矩阵的运算，所以需要Python的NumPy（NumericalPython）库的支持，NumPy是Python的一个扩展程序库，支持高维数组和矩阵运算，除此外也对数组运算提供大量的数学函数库。安装Numpy的方式有很多，可以用Pip或Apt-get等进行安装，因为除了这个库还有一些依赖库，比如Matplotlib等，这里我们使用数据分析较常用的Anaconda这个支持Linux,Windows和Mac系统，用于大规模数据处理,预测分析和科学计算并致力于简化包的管理和部署的Python免费发行版。
Anaconda的安装比较简单，这里就不做赘述，为了方便直接使用Dockerhub上比较受欢迎的continuumio/anaconda镜像作为基础镜像构建我们的微服务镜像，Dockerfile如图2-9和图2-10所示。
图2-9基于K最近邻密码强度评测Dockerfile
构建镜像：dockerbuild-tlocaltest.registry..com:9000/knnpassord:v1.
运行测试：dockerrun-d-p6666:6666raysail/knnpassord:v1
提交仓库：dockerpushlocaltest.registry.com:9000/knnpassord:v1
图2-10基于决策树密码强度评测Dockerfile
构建镜像：dockerbuild-tlocaltest.registry..com:9000/dtpassord:v1.
运行测试：dockerrun-d-p8888:6666raysail/dtpassord:v1
提交仓库：dockerpushlocaltest.registry.com:9000/dtpassord:v1
4.2Kubnerntes中运行为服务
分别创建副本数为3的knn-passwordDeployment,descisiontree-passwordDepoyment，如图2-11和图2-12，并分别创建两个service如图2-13和图2-14：
图2-11基于KNN的密码强度评测微服务Deployment
图2-12基于决策树的密码强度评测微服务Deployment
图2-13基于KNN的密码强度评测微服务Service
图2-14基于决策树的密码强度评测微服务Service
kubnerntes资源查看如图2-15。
图2-15密码评测微服务创建后kubnertespod和service视图
用kubectldescribe命令查看服务可以看到每个服务后端挂载有三个pod，以实现容灾和负载均衡，具体如图2-16所示。
图2-16kubectldescribe命令查看服务视图
4.3验证服务可用性及准确性
两个密码强度评测微服务的protobuf定义如图2-17和图2-18所示。
图2-17K最近邻密码强度评测Protobuf定义
图2-18决策树密码强度评测Protobuf定义
分别用golang和php的客户端测试基于Knn的密码强度评测微服务和基于决策树的密码强度评测微服务可以正常返回。用如下命令分别生成golang客户端桩函数和php客户端桩函数：
protoc--go_out=plugins=grpc:././password.protoprotoc--php_out=./--plugin=protoc-gen-grpc=/usr/local/bin/grpc_php_plugin./password.proto
5.持续集成和滚动更新实现
5.1基于Gitolite的Hook技术
主要算法思想是利用Git的服务端Hook——post-receive来触发Push代码后的操作，也就是提交代码后可以根据分支以及具体的Log中的关键字来相应的执行包括但不限于单元测试，构建镜像，自动部署等操作。
具体可参加如下Shell脚本（处理阶段的自动化脚本处理和Jinkens触发处理注释了，可选择其中一种或别的方式）
5.2基于Kubeapi的滚动升级
具体主要ShellCode如图2-19所示。
图2-19Kubeapi主要Shellcode
总结与展望
在以上研究基础上，经过学习考试，通过了Google和CNCF（CloudNativeComputingFoundation）联合推出的CKA（CertifiedKubernetesAdministrator）认证，通过备考的大量实践演练，进一步加深了自动部署、扩展和管理容器化的开源框架Kubernetes原理的认知，也更加相信未来此系统会被大规模采纳并应用到更多的企业和技术领域。此外在云计算和大数据迅猛发展的今天，机器学习被越来越多的应用到各行各业中，而机器学习应用的工程化，自动化和平台化亟需普及和建设，这也是依托Kubernetes集群进行基于机器学习的微服务实践的原因，当然密码作为一直都很重要的安全行业的重要组成部分，作为本文技术架构下的核心业务部分也是本文的重点工作。
参考文献
[1]J.Bonneau,C.Herley,P.vanOorschot,andF.Stajano,“Passwordsandtheevolutionofimperfectauthentication,”Commun.oftheACM,vol.58,no.7,pp.78–87,2015.
[2]J.Yan,A.F.Blackwell,R.J.Anderson,andA.Grant,“Passwordmemorabilityandsecurity:Empiricalresults.”IEEESecur.&priv.,vol.2,no.5,pp.25–31,2004.
[3]W.Cheswick,“Rethinkingpasswords,”Commun.oftheACM,vol.56,no.2,pp.40–44,2013.
[4]严霄凤.基于熵的密码强度估计.网络安全技术与应用,2012(11):36-38
[5]DingWang,DebiaoHe,HaiboCheng,PingWang.fuzzyPSM-ANewPasswordStrengthMeterUsingFuzzyProbabilisticContext-FreeGrammars.IEEE/IFIPInternationalConferenceonDependableSystemsandNetworks,2016:595-606
[6]周志华.机器学习:Machinelearning[M].清华大学出版社,2016.
[7]VijayaMS,JamunaKS,KarpagavalliS.PasswordStrengthPredictionUsingSupervisedMachineLearningTechniques[C]//InternationalConferenceonAdvancesinComputing.IEEE,2010.
[8]GSuganya，SKarpgavalli，VChristina.ProactivePasswordStrengthAnalyzerUsingFiltersandMachineLearningTechniques.InternationalConferenceonAdvancesinComputing,2010:401-405
[9](美)米歇尔(MitchellT.M.)著，曾华军等译.计算机科学丛书:机器学习.北京：机械工业出版社，2003.1,8:165~177