在设置数据库主键时有没有什么好的实践经验?

回复

数据库zkbhj 回复了问题 • 1 人关注 • 1 个回复 • 125 次浏览 • 2018-09-19 21:50 • 来自相关话题

Yii2中“事务”中只有一张表数据更新成功了却没有回滚?什么原因造成的?

回复

Yii框架zkbhj 回复了问题 • 1 人关注 • 1 个回复 • 196 次浏览 • 2018-09-19 16:12 • 来自相关话题

什么是双因子认证?双因子认证的好处是什么?

专业名词zkbhj 发表了文章 • 1 个评论 • 269 次浏览 • 2018-09-19 15:08 • 来自相关话题

双因子认证(2FA)是指结合密码以及实物(信用卡、SMS手机、令牌或指纹等生物标志)两种条件对用户的身份进行认证的方法。这种方法已经得到了企业的广泛采用,特别是在对数据进行远程访问时,但在其它领域应用还十分有限。双因子身份认证的推广之所以受阻,主要是由于其需要使用额外的工具,而这一条件为IT和技术支持人员带来了不小的负担。其批评者还指出,这种安全保障措施仍然很容易遭受攻击,即在非常小的时间周期内,这种技术很容易受到中间人(man-in-the-middle)攻击(这也是采用严格SSL处理的主要原因)。实际上,除了这些障碍以外,现在我们已经开始认识到,不采用双因子认证所带来的隐含成本远远比采用双因子认证所需要的成本高得多。






双因子身份认证是确保远程访问安全性的最佳实践方式,但是这种技术也给了一些网络犯罪分子可乘之机。如果攻击者在获取到了大量身份凭证的情况下,他们就可以伪装成合法用户,而且还可以躲避安全防护软件的检测。很多公司都认为双因子认证机制是绝对可靠的,而且也没有采取一定的安全预防措施来防御攻击者的攻击以及系统后门。

在这篇文章中,我们将会站在攻击者的角度来对双因子身份验证机制进行从浅至深的分析,我们希望这篇文章能够帮助安全研究人员解决这项技术中目前所存在的一些问题。我将会对远程绕过双因子身份验证技术进行讨论,并且向大家描述如何绕过远程访问设备的双因子身份验证机制,并从内部网络环境的设备中窃取数据。

1)K.I.S.S-简单,有效

入侵设备的远程访问控制是攻击者首要解决的问题,因为它可以给攻击者提供设备的访问权限,并且降低被监测到的可能性。在合法远程访问工具的帮助下,攻击者不仅可以在目标主机中执行控制命令,而且还可以在身份验证机制的掩护下进行其他的一些攻击活动。

在某些较为困难的情况下,我们可以使用一些比较直接的方法来获取到我们所需的凭证:让目标用户代替我们来进行操作。我们只需进行一些简单的设置就可以制作一个完美的陷阱。

在下图中,我们可以看到两个不同的VPN登录页面。其中一个是公司的合法登录网站,另一个是由攻击者伪造的虚假登录页面。你能发现这两者之间的区别吗?





 
分辨不出吗?没错,你的客户也一样分辨不出。在社会工程学工具(SET)的帮助下,任何人都可以快速地复制出一个外部页面来欺骗用户(攻击者只需要将HTML页面中的本地资源地址(“/home/image/logo.png”)修改成外部引用地址(“mycompany.com/home/image/logo.png”)就可以了)。在一次完美的网络钓鱼攻击中,你可以引诱目标用户访问你所克隆出的虚假VPN身份验证页面,并且得到所有你需要的信息:用户名,密码,甚至是令牌码!

如果攻击者的操作速度足够快,那么他们还可以将凭证提交至虚假的VPN页面,然后利用这些信息来登录真实的VPN。如下图所示,攻击者可以将登录提交请求重定向至一个PHP脚本,然后这个脚本就会将提交过来的用户名,密码,以及其他的一些元数据写入服务器的日志文件中,这样攻击者就可以检测并获取到用户所提交的双因子身份验证信息了。




当攻击者通过了VPN的身份验证之后,他们就可以在安全检测软件检测到钓鱼攻击并进行安全响应之前,在目标主机中实现提权并获取到敏感数据。

2)电子邮件就是我们的敌人

数字令牌通常会需要一个同步代码,而为了保证其有效性,每一名用户的令牌都只会有一个唯一的同步码与之对应。同步码和算法是保证令牌安全性的因素,而且这两个因素也可以确保用户令牌能够与身份验证服务器的要求所匹配。当用户的VPN访问请求通过批准之后,很多公司会选择使用一种简单和友好的方式来向用户发送通知类的电子邮件。这些电子邮件中通常会包含有“seed“密钥和安装说明。但对于安全团队来说不幸的是,用户通常在阅读完这类电子邮件之后,却忘记将其删除了,这些电子邮件就这样躺在了用户的收件箱之中,等待着攻击者前来窃取。

攻击者可以在用户的电子邮箱中搜索敏感文件和有价值的信息(包括硬盘中的.PST和.OST文件)。在大多数情况下,攻击者只需要使用一个简单的PowerShell脚本就可以搜索用户邮箱中的敏感文件以及与RSA软令牌相关的.sdtid文件了。

3)双因子身份验证机制中的紧急模式

在很多的双因子身份验证产品中,都提供有一个名为“紧急访问”的代码,这种运行模式实际上是一种身份验证机制,如果用户丢失了令牌,但是又急需对数据进行远程访问,那么这种机制也可以允许用户进行临时性的VPN访问。下图显示的就是紧急访问模式的操作界面截图:




如上图所示,系统提供了一个身份验证的修复机制。对于攻击者而言,攻击者可以利用这种机制来远程访问目标系统。这些紧急访问码是非常不安全的,因为他们的有效日期可以被修改,这样一来,攻击者就可以利用这些紧急访问码来获取到目标系统的永久访问权限了。

总结

对于一名经验丰富的攻击者来说,他们有很多种方法可以对目标进行攻击,并绕过那些所谓的“安全防护措施“。

不幸的是,很多公司太过于相信那些所谓的安全解决方案了,例如双因子身份验证。如果安全技术人员没有采取一些必要的安全保障措施,那么这种安全技术也不能保证公司的安全。如果安全技术人员忽略了这一点,那么攻击者就可以利用如上文所述的一些攻击方法破坏双因子身份验证技术本该带来的安全性。

在此,我还需要感谢Andrew Burkhardt, Evan Peña, 以及Justin Prosco为这篇文章所做出的贡献。
 
文章原文:https://www.fireeye.com/blog/t ... .html 查看全部
双因子认证(2FA)是指结合密码以及实物(信用卡、SMS手机、令牌或指纹等生物标志)两种条件对用户的身份进行认证的方法。这种方法已经得到了企业的广泛采用,特别是在对数据进行远程访问时,但在其它领域应用还十分有限。双因子身份认证的推广之所以受阻,主要是由于其需要使用额外的工具,而这一条件为IT和技术支持人员带来了不小的负担。其批评者还指出,这种安全保障措施仍然很容易遭受攻击,即在非常小的时间周期内,这种技术很容易受到中间人(man-in-the-middle)攻击(这也是采用严格SSL处理的主要原因)。实际上,除了这些障碍以外,现在我们已经开始认识到,不采用双因子认证所带来的隐含成本远远比采用双因子认证所需要的成本高得多。

t01fc4acdc6ee66ec6e.jpg


双因子身份认证是确保远程访问安全性的最佳实践方式,但是这种技术也给了一些网络犯罪分子可乘之机。如果攻击者在获取到了大量身份凭证的情况下,他们就可以伪装成合法用户,而且还可以躲避安全防护软件的检测。很多公司都认为双因子认证机制是绝对可靠的,而且也没有采取一定的安全预防措施来防御攻击者的攻击以及系统后门。

在这篇文章中,我们将会站在攻击者的角度来对双因子身份验证机制进行从浅至深的分析,我们希望这篇文章能够帮助安全研究人员解决这项技术中目前所存在的一些问题。我将会对远程绕过双因子身份验证技术进行讨论,并且向大家描述如何绕过远程访问设备的双因子身份验证机制,并从内部网络环境的设备中窃取数据。

1)K.I.S.S-简单,有效

入侵设备的远程访问控制是攻击者首要解决的问题,因为它可以给攻击者提供设备的访问权限,并且降低被监测到的可能性。在合法远程访问工具的帮助下,攻击者不仅可以在目标主机中执行控制命令,而且还可以在身份验证机制的掩护下进行其他的一些攻击活动。

在某些较为困难的情况下,我们可以使用一些比较直接的方法来获取到我们所需的凭证:让目标用户代替我们来进行操作。我们只需进行一些简单的设置就可以制作一个完美的陷阱。

在下图中,我们可以看到两个不同的VPN登录页面。其中一个是公司的合法登录网站,另一个是由攻击者伪造的虚假登录页面。你能发现这两者之间的区别吗?

t01775f75e07e0a35a7.png

 
分辨不出吗?没错,你的客户也一样分辨不出。在社会工程学工具(SET)的帮助下,任何人都可以快速地复制出一个外部页面来欺骗用户(攻击者只需要将HTML页面中的本地资源地址(“/home/image/logo.png”)修改成外部引用地址(“mycompany.com/home/image/logo.png”)就可以了)。在一次完美的网络钓鱼攻击中,你可以引诱目标用户访问你所克隆出的虚假VPN身份验证页面,并且得到所有你需要的信息:用户名,密码,甚至是令牌码!

如果攻击者的操作速度足够快,那么他们还可以将凭证提交至虚假的VPN页面,然后利用这些信息来登录真实的VPN。如下图所示,攻击者可以将登录提交请求重定向至一个PHP脚本,然后这个脚本就会将提交过来的用户名,密码,以及其他的一些元数据写入服务器的日志文件中,这样攻击者就可以检测并获取到用户所提交的双因子身份验证信息了。
fig2.png

当攻击者通过了VPN的身份验证之后,他们就可以在安全检测软件检测到钓鱼攻击并进行安全响应之前,在目标主机中实现提权并获取到敏感数据。

2)电子邮件就是我们的敌人

数字令牌通常会需要一个同步代码,而为了保证其有效性,每一名用户的令牌都只会有一个唯一的同步码与之对应。同步码和算法是保证令牌安全性的因素,而且这两个因素也可以确保用户令牌能够与身份验证服务器的要求所匹配。当用户的VPN访问请求通过批准之后,很多公司会选择使用一种简单和友好的方式来向用户发送通知类的电子邮件。这些电子邮件中通常会包含有“seed“密钥和安装说明。但对于安全团队来说不幸的是,用户通常在阅读完这类电子邮件之后,却忘记将其删除了,这些电子邮件就这样躺在了用户的收件箱之中,等待着攻击者前来窃取。

攻击者可以在用户的电子邮箱中搜索敏感文件和有价值的信息(包括硬盘中的.PST和.OST文件)。在大多数情况下,攻击者只需要使用一个简单的PowerShell脚本就可以搜索用户邮箱中的敏感文件以及与RSA软令牌相关的.sdtid文件了。

3)双因子身份验证机制中的紧急模式

在很多的双因子身份验证产品中,都提供有一个名为“紧急访问”的代码,这种运行模式实际上是一种身份验证机制,如果用户丢失了令牌,但是又急需对数据进行远程访问,那么这种机制也可以允许用户进行临时性的VPN访问。下图显示的就是紧急访问模式的操作界面截图:
fig9.png

如上图所示,系统提供了一个身份验证的修复机制。对于攻击者而言,攻击者可以利用这种机制来远程访问目标系统。这些紧急访问码是非常不安全的,因为他们的有效日期可以被修改,这样一来,攻击者就可以利用这些紧急访问码来获取到目标系统的永久访问权限了。

总结

对于一名经验丰富的攻击者来说,他们有很多种方法可以对目标进行攻击,并绕过那些所谓的“安全防护措施“。

不幸的是,很多公司太过于相信那些所谓的安全解决方案了,例如双因子身份验证。如果安全技术人员没有采取一些必要的安全保障措施,那么这种安全技术也不能保证公司的安全。如果安全技术人员忽略了这一点,那么攻击者就可以利用如上文所述的一些攻击方法破坏双因子身份验证技术本该带来的安全性。

在此,我还需要感谢Andrew Burkhardt, Evan Peña, 以及Justin Prosco为这篇文章所做出的贡献。
 
文章原文:https://www.fireeye.com/blog/t ... .html

JWT:完全前后端分离的项目如何做用户身份验证更安全?看这篇就够了!

前端开发zkbhj 发表了文章 • 0 个评论 • 281 次浏览 • 2018-09-19 14:48 • 来自相关话题

在前后端分离开发时为什么需要用户认证呢?原因是由于HTTP协定是不储存状态的(stateless),这意味着当我们透过帐号密码验证一个使用者时,当下一个request请求时它就把刚刚的资料忘了。于是我们的程序就不知道谁是谁,就要再验证一次。所以为了保证系统安全,我们就需要验证用户否处于登录状态。

传统方式

前后端分离通过Restful API进行数据交互时,如何验证用户的登录信息及权限。在原来的项目中,使用的是最传统也是最简单的方式,前端登录,后端根据用户信息生成一个token,并保存这个 token 和对应的用户id到数据库或Session中,接着把 token 传给用户,存入浏览器 cookie,之后浏览器请求带上这个cookie,后端根据这个cookie值来查询用户,验证是否过期。

但这样做问题就很多,如果我们的页面出现了 XSS 漏洞,由于 cookie 可以被 JavaScript 读取,XSS 漏洞会导致用户 token 泄露,而作为后端识别用户的标识,cookie 的泄露意味着用户信息不再安全。尽管我们通过转义输出内容,使用 CDN 等可以尽量避免 XSS 注入,但谁也不能保证在大型的项目中不会出现这个问题。

在设置 cookie 的时候,其实你还可以设置 httpOnly 以及 secure 项。设置 httpOnly 后 cookie 将不能被 JS 读取,浏览器会自动的把它加在请求的 header 当中,设置 secure 的话,cookie 就只允许通过 HTTPS 传输。secure 选项可以过滤掉一些使用 HTTP 协议的 XSS 注入,但并不能完全阻止。

httpOnly 选项使得 JS 不能读取到 cookie,那么 XSS 注入的问题也基本不用担心了。但设置 httpOnly 就带来了另一个问题,就是很容易的被 XSRF,即跨站请求伪造。当你浏览器开着这个页面的时候,另一个页面可以很容易的跨站请求这个页面的内容。因为 cookie 默认被发了出去。

另外,如果将验证信息保存在数据库中,后端每次都需要根据token查出用户id,这就增加了数据库的查询和存储开销。若把验证信息保存在session中,有加大了服务器端的存储压力。那我们可不可以不要服务器去查询呢?如果我们生成token遵循一定的规律,比如我们使用对称加密算法来加密用户id形成token,那么服务端以后其实只要解密该token就可以知道用户的id是什么了。不过呢,我只是举个例子而已,要是真这么做,只要你的对称加密算法泄露了,其他人可以通过这种加密方式进行伪造token,那么所有用户信息都不再安全了。恩,那用非对称加密算法来做呢,其实现在有个规范就是这样做的,就是我们接下来要介绍的 JWT。

Json Web Token(JWT)

JWT 是一个开放标准(RFC 7519),它定义了一种用于简洁,自包含的用于通信双方之间以 JSON 对象的形式安全传递信息的方法。JWT 可以使用 HMAC 算法或者是 RSA 的公钥密钥对进行签名。它具备两个特点:

简洁(Compact)

可以通过URL, POST 参数或者在 HTTP header 发送,因为数据量小,传输速度快

自包含(Self-contained)

负载中包含了所有用户所需要的信息,避免了多次查询数据库


JWT 组成





Header 头部

头部包含了两部分,token 类型和采用的加密算法
 {
"alg": "HS256",
"typ": "JWT"
}它会使用 Base64 编码组成 JWT 结构的第一部分,如果你使用Node.js,可以用Node.js的包base64url来得到这个字符串。

Base64是一种编码,也就是说,它是可以被翻译回原来的样子来的。它并不是一种加密过程。

Payload 负载

这部分就是我们存放信息的地方了,你可以把用户 ID 等信息放在这里,JWT 规范里面对这部分有进行了比较详细的介绍,常用的由 iss(签发者),exp(过期时间),sub(面向的用户),aud(接收方),iat(签发时间)。
 {
"iss": "lion1ou JWT",
"iat": 1441593502,
"exp": 1441594722,
"aud": "www.example.com",
"sub": "lion1ou@163.com"
}同样的,它会使用 Base64 编码组成 JWT 结构的第二部分

Signature 签名

前面两部分都是使用 Base64 进行编码的,即前端可以解开知道里面的信息。Signature 需要使用编码后的 header 和 payload 以及我们提供的一个密钥,然后使用 header 中指定的签名算法(HS256)进行签名。签名的作用是保证 JWT 没有被篡改过。

三个部分通过.连接在一起就是我们的 JWT 了,它可能长这个样子,长度貌似和你的加密算法和私钥有关系。eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJpZCI6IjU3ZmVmMTY0ZTU0YWY2NGZmYzUzZGJkNSIsInhzcmYiOiI0ZWE1YzUwOGE2NTY2ZTc2MjQwNTQzZjhmZWIwNmZkNDU3Nzc3YmUzOTU0OWM0MDE2NDM2YWZkYTY1ZDIzMzBlIiwiaWF0IjoxNDc2NDI3OTMzfQ.PA3QjeyZSUh7H0GfE0vJaKW4LjKJuC3dVLQiY4hii8s

其实到这一步可能就有人会想了,HTTP 请求总会带上 token,这样这个 token 传来传去占用不必要的带宽啊。如果你这么想了,那你可以去了解下 HTTP2,HTTP2 对头部进行了压缩,相信也解决了这个问题。

签名的目的

最后一步签名的过程,实际上是对头部以及负载内容进行签名,防止内容被窜改。如果有人对头部以及负载的内容解码之后进行修改,再进行编码,最后加上之前的签名组合形成新的JWT的话,那么服务器端会判断出新的头部和负载形成的签名和JWT附带上的签名是不一样的。如果要对新的头部和负载进行签名,在不知道服务器加密时用的密钥的话,得出来的签名也是不一样的。

信息暴露

在这里大家一定会问一个问题:Base64是一种编码,是可逆的,那么我的信息不就被暴露了吗?

是的。所以,在JWT中,不应该在负载里面加入任何敏感的数据。在上面的例子中,我们传输的是用户的User ID。这个值实际上不是什么敏感内容,一般情况下被知道也是安全的。但是像密码这样的内容就不能被放在JWT中了。如果将用户的密码放在了JWT中,那么怀有恶意的第三方通过Base64解码就能很快地知道你的密码了。

因此JWT适合用于向Web应用传递一些非敏感信息。JWT还经常用于设计用户认证和授权系统,甚至实现Web应用的单点登录。

JWT 使用




 
首先,前端通过Web表单将自己的用户名和密码发送到后端的接口。这一过程一般是一个HTTP POST请求。建议的方式是通过SSL加密的传输(https协议),从而避免敏感信息被嗅探。后端核对用户名和密码成功后,将用户的id等其他信息作为JWT Payload(负载),将其与头部分别进行Base64编码拼接后签名,形成一个JWT。形成的JWT就是一个形同lll.zzz.xxx的字符串。后端将JWT字符串作为登录成功的返回结果返回给前端。前端可以将返回的结果保存在localStorage或sessionStorage上,退出登录时前端删除保存的JWT即可。前端在每次请求时将JWT放入HTTP Header中的Authorization位。(解决XSS和XSRF问题)后端检查是否存在,如存在验证JWT的有效性。例如,检查签名是否正确;检查Token是否过期;检查Token的接收方是否是自己(可选)。验证通过后后端使用JWT中包含的用户信息进行其他逻辑操作,返回相应结果。

和Session方式存储id的差异

Session方式存储用户id的最大弊病在于Session是存储在服务器端的,所以需要占用大量服务器内存,对于较大型应用而言可能还要保存许多的状态。一般而言,大型应用还需要借助一些KV数据库和一系列缓存机制来实现Session的存储。

而JWT方式将用户状态分散到了客户端中,可以明显减轻服务端的内存压力。除了用户id之外,还可以存储其他的和用户相关的信息,例如该用户是否是管理员、用户所在的分组等。虽说JWT方式让服务器有一些计算压力(例如加密、编码和解码),但是这些压力相比磁盘存储而言可能就不算什么了。具体是否采用,需要在不同场景下用数据说话。

单点登录

Session方式来存储用户id,一开始用户的Session只会存储在一台服务器上。对于有多个子域名的站点,每个子域名至少会对应一台不同的服务器,例如:www.taobao.com,nv.taobao.com,nz.taobao.com,login.taobao.com。所以如果要实现在login.taobao.com登录后,在其他的子域名下依然可以取到Session,这要求我们在多台服务器上同步Session。使用JWT的方式则没有这个问题的存在,因为用户的状态已经被传送到了客户端。

总结

JWT的主要作用在于(一)可附带用户信息,后端直接通过JWT获取相关信息。(二)使用本地保存,通过HTTP Header中的Authorization位提交验证。但其实关于JWT存放到哪里一直有很多讨论,有人说存放到本地存储,有人说存 cookie。个人偏向于放在本地存储,如果你有什么意见和看法欢迎提出。

参考文档:
https://segmentfault.com/a/1190000005783306 
https://ruiming.me/authentication-of-frontend-backend-separate-application/ 
 
总结和摘录自:
https://blog.csdn.net/kevin_lc ... 46723 查看全部
在前后端分离开发时为什么需要用户认证呢?原因是由于HTTP协定是不储存状态的(stateless),这意味着当我们透过帐号密码验证一个使用者时,当下一个request请求时它就把刚刚的资料忘了。于是我们的程序就不知道谁是谁,就要再验证一次。所以为了保证系统安全,我们就需要验证用户否处于登录状态。

传统方式

前后端分离通过Restful API进行数据交互时,如何验证用户的登录信息及权限。在原来的项目中,使用的是最传统也是最简单的方式,前端登录,后端根据用户信息生成一个token,并保存这个 token 和对应的用户id到数据库或Session中,接着把 token 传给用户,存入浏览器 cookie,之后浏览器请求带上这个cookie,后端根据这个cookie值来查询用户,验证是否过期。

但这样做问题就很多,如果我们的页面出现了 XSS 漏洞,由于 cookie 可以被 JavaScript 读取,XSS 漏洞会导致用户 token 泄露,而作为后端识别用户的标识,cookie 的泄露意味着用户信息不再安全。尽管我们通过转义输出内容,使用 CDN 等可以尽量避免 XSS 注入,但谁也不能保证在大型的项目中不会出现这个问题。

在设置 cookie 的时候,其实你还可以设置 httpOnly 以及 secure 项。设置 httpOnly 后 cookie 将不能被 JS 读取,浏览器会自动的把它加在请求的 header 当中,设置 secure 的话,cookie 就只允许通过 HTTPS 传输。secure 选项可以过滤掉一些使用 HTTP 协议的 XSS 注入,但并不能完全阻止。

httpOnly 选项使得 JS 不能读取到 cookie,那么 XSS 注入的问题也基本不用担心了。但设置 httpOnly 就带来了另一个问题,就是很容易的被 XSRF,即跨站请求伪造。当你浏览器开着这个页面的时候,另一个页面可以很容易的跨站请求这个页面的内容。因为 cookie 默认被发了出去。

另外,如果将验证信息保存在数据库中,后端每次都需要根据token查出用户id,这就增加了数据库的查询和存储开销。若把验证信息保存在session中,有加大了服务器端的存储压力。那我们可不可以不要服务器去查询呢?如果我们生成token遵循一定的规律,比如我们使用对称加密算法来加密用户id形成token,那么服务端以后其实只要解密该token就可以知道用户的id是什么了。不过呢,我只是举个例子而已,要是真这么做,只要你的对称加密算法泄露了,其他人可以通过这种加密方式进行伪造token,那么所有用户信息都不再安全了。恩,那用非对称加密算法来做呢,其实现在有个规范就是这样做的,就是我们接下来要介绍的 JWT。

Json Web Token(JWT)

JWT 是一个开放标准(RFC 7519),它定义了一种用于简洁,自包含的用于通信双方之间以 JSON 对象的形式安全传递信息的方法。JWT 可以使用 HMAC 算法或者是 RSA 的公钥密钥对进行签名。它具备两个特点:


简洁(Compact)

可以通过URL, POST 参数或者在 HTTP header 发送,因为数据量小,传输速度快

自包含(Self-contained)

负载中包含了所有用户所需要的信息,避免了多次查询数据库



JWT 组成

006tNc79gy1fbv54tfilmj31120b2wl9.jpg

Header 头部

头部包含了两部分,token 类型和采用的加密算法
 
{
"alg": "HS256",
"typ": "JWT"
}
它会使用 Base64 编码组成 JWT 结构的第一部分,如果你使用Node.js,可以用Node.js的包base64url来得到这个字符串。


Base64是一种编码,也就是说,它是可以被翻译回原来的样子来的。它并不是一种加密过程。


Payload 负载

这部分就是我们存放信息的地方了,你可以把用户 ID 等信息放在这里,JWT 规范里面对这部分有进行了比较详细的介绍,常用的由 iss(签发者),exp(过期时间),sub(面向的用户),aud(接收方),iat(签发时间)。
 
{
"iss": "lion1ou JWT",
"iat": 1441593502,
"exp": 1441594722,
"aud": "www.example.com",
"sub": "lion1ou@163.com"
}
同样的,它会使用 Base64 编码组成 JWT 结构的第二部分

Signature 签名

前面两部分都是使用 Base64 进行编码的,即前端可以解开知道里面的信息。Signature 需要使用编码后的 header 和 payload 以及我们提供的一个密钥,然后使用 header 中指定的签名算法(HS256)进行签名。签名的作用是保证 JWT 没有被篡改过。

三个部分通过.连接在一起就是我们的 JWT 了,它可能长这个样子,长度貌似和你的加密算法和私钥有关系。
eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJpZCI6IjU3ZmVmMTY0ZTU0YWY2NGZmYzUzZGJkNSIsInhzcmYiOiI0ZWE1YzUwOGE2NTY2ZTc2MjQwNTQzZjhmZWIwNmZkNDU3Nzc3YmUzOTU0OWM0MDE2NDM2YWZkYTY1ZDIzMzBlIiwiaWF0IjoxNDc2NDI3OTMzfQ.PA3QjeyZSUh7H0GfE0vJaKW4LjKJuC3dVLQiY4hii8s

其实到这一步可能就有人会想了,HTTP 请求总会带上 token,这样这个 token 传来传去占用不必要的带宽啊。如果你这么想了,那你可以去了解下 HTTP2,HTTP2 对头部进行了压缩,相信也解决了这个问题。

签名的目的

最后一步签名的过程,实际上是对头部以及负载内容进行签名,防止内容被窜改。如果有人对头部以及负载的内容解码之后进行修改,再进行编码,最后加上之前的签名组合形成新的JWT的话,那么服务器端会判断出新的头部和负载形成的签名和JWT附带上的签名是不一样的。如果要对新的头部和负载进行签名,在不知道服务器加密时用的密钥的话,得出来的签名也是不一样的。

信息暴露

在这里大家一定会问一个问题:Base64是一种编码,是可逆的,那么我的信息不就被暴露了吗?

是的。所以,在JWT中,不应该在负载里面加入任何敏感的数据。在上面的例子中,我们传输的是用户的User ID。这个值实际上不是什么敏感内容,一般情况下被知道也是安全的。但是像密码这样的内容就不能被放在JWT中了。如果将用户的密码放在了JWT中,那么怀有恶意的第三方通过Base64解码就能很快地知道你的密码了。

因此JWT适合用于向Web应用传递一些非敏感信息。JWT还经常用于设计用户认证和授权系统,甚至实现Web应用的单点登录。

JWT 使用

006tNc79gy1fbv63pzqocj30pj0h8t9m.jpg
 
  1. 首先,前端通过Web表单将自己的用户名和密码发送到后端的接口。这一过程一般是一个HTTP POST请求。建议的方式是通过SSL加密的传输(https协议),从而避免敏感信息被嗅探。
  2. 后端核对用户名和密码成功后,将用户的id等其他信息作为JWT Payload(负载),将其与头部分别进行Base64编码拼接后签名,形成一个JWT。形成的JWT就是一个形同lll.zzz.xxx的字符串。
  3. 后端将JWT字符串作为登录成功的返回结果返回给前端。前端可以将返回的结果保存在localStorage或sessionStorage上,退出登录时前端删除保存的JWT即可。
  4. 前端在每次请求时将JWT放入HTTP Header中的Authorization位。(解决XSS和XSRF问题)
  5. 后端检查是否存在,如存在验证JWT的有效性。例如,检查签名是否正确;检查Token是否过期;检查Token的接收方是否是自己(可选)。
  6. 验证通过后后端使用JWT中包含的用户信息进行其他逻辑操作,返回相应结果。


和Session方式存储id的差异

Session方式存储用户id的最大弊病在于Session是存储在服务器端的,所以需要占用大量服务器内存,对于较大型应用而言可能还要保存许多的状态。一般而言,大型应用还需要借助一些KV数据库和一系列缓存机制来实现Session的存储。

而JWT方式将用户状态分散到了客户端中,可以明显减轻服务端的内存压力。除了用户id之外,还可以存储其他的和用户相关的信息,例如该用户是否是管理员、用户所在的分组等。虽说JWT方式让服务器有一些计算压力(例如加密、编码和解码),但是这些压力相比磁盘存储而言可能就不算什么了。具体是否采用,需要在不同场景下用数据说话。

单点登录

Session方式来存储用户id,一开始用户的Session只会存储在一台服务器上。对于有多个子域名的站点,每个子域名至少会对应一台不同的服务器,例如:www.taobao.com,nv.taobao.com,nz.taobao.com,login.taobao.com。所以如果要实现在login.taobao.com登录后,在其他的子域名下依然可以取到Session,这要求我们在多台服务器上同步Session。使用JWT的方式则没有这个问题的存在,因为用户的状态已经被传送到了客户端。

总结

JWT的主要作用在于(一)可附带用户信息,后端直接通过JWT获取相关信息。(二)使用本地保存,通过HTTP Header中的Authorization位提交验证。但其实关于JWT存放到哪里一直有很多讨论,有人说存放到本地存储,有人说存 cookie。个人偏向于放在本地存储,如果你有什么意见和看法欢迎提出。

参考文档:
https://segmentfault.com/a/1190000005783306 
https://ruiming.me/authentication-of-frontend-backend-separate-application/ 
 
总结和摘录自:
https://blog.csdn.net/kevin_lc ... 46723

JavaScript如何识别当前页面是否处于激活状态?

回复

前端开发zkbhj 回复了问题 • 1 人关注 • 1 个回复 • 129 次浏览 • 2018-09-18 19:29 • 来自相关话题

今年22号台风“山竹”在澳门等级为十号风球,十号风球指的是什么?

回复

随手记zkbhj 回复了问题 • 1 人关注 • 1 个回复 • 333 次浏览 • 2018-09-16 23:06 • 来自相关话题

如何在Linux安装java运行环境?

回复

Javazkbhj 回复了问题 • 1 人关注 • 1 个回复 • 113 次浏览 • 2018-09-16 22:52 • 来自相关话题

PHP升级7.2之后需要注意的“坑”

PHPzkbhj 发表了文章 • 0 个评论 • 285 次浏览 • 2018-09-12 20:25 • 来自相关话题

最近升级了PHP版本,从7.1升级到7.2,升级前版本:
PHP 7.1.14 (cli) (built: Feb 2 2018 08:42:59) ( NTS )
Copyright (c) 1997-2018 The PHP Group
Zend Engine v3.1.0, Copyright (c) 1998-2018 Zend Technologies
with Zend OPcache v7.1.14, Copyright (c) 1999-2018, by Zend Technologies
with Xdebug v2.6.0, Copyright (c) 2002-2018, by Derick Rethans升级后版本:
PHP 7.2.2 (cli) (built: Feb 24 2018 17:51:12) ( ZTS DEBUG )
Copyright (c) 1997-2018 The PHP Group
Zend Engine v3.2.0, Copyright (c) 1998-2018 Zend Technologies
with Zend OPcache v7.2.2, Copyright (c) 1999-2018, by Zend Technologies升级完成之后发现有几个框架在使用时都出现了问题,主要原因集中在7.2之后废弃了一些功能,下面列出几个常见的问题:

1、each函数已被废弃:

之前版本写法:<?php
$array = array();
each($array);

// Deprecated: The each() function is deprecated. This message will be suppressed on further calls在7.2版本中会提示过时,可以使用foreach替代each方法,也可以自己修改each方法替代:
<?php
function func_new_each(&$array){
$res = array();
$key = key($array);
if($key !== null){
next($array);
$res[1] = $res['value'] = $array[$key];
$res[0] = $res['key'] = $key;
}else{
$res = false;
}
return $res;
}
2、当传递一个无效参数时,count()函数将抛出warning警告:

之前版本写法<?php
count('');

// Warning: count(): Parameter must be an array or an object that implements Countable在7.2版本中将严格执行类型区分,参数类型不正确,将会出现警告,所以需要在使用count方法时注意参数的值,不过也可以通过自己修改方法来替代(不建议):
<?php
function func_new_count($array_or_countable,$mode = COUNT_NORMAL){
if(is_array($array_or_countable) || is_object($array_or_countable)){
return count($array_or_countable, $mode);
}else{
return 0;
}
}3、create_function被废弃,可以用匿名函数来代替:

之前版本写法:<?php
$newfunc = create_function('$a,$b', 'return "ln($a) + ln($b) = " . log($a * $b);');
echo "New anonymous function: $newfunc\n";
echo $newfunc(2, M_E) . "\n";
// outputs
// New anonymous function: lambda_1
// ln(2) + ln(2.718281828459) = 1.6931471805599

// Warning This function has been DEPRECATED as of PHP 7.2.0. Relying on this function is highly discouraged.在7.2版本中会有警告提示,可修改为匿名函数来替代:
<?php
$newfunc = function ($a,$b){
return "ln($a) + ln($b) = " . log($a * $b);
};
echo $newfunc(2, M_E) . "\n";以上就是升级之后暂时遇到的几个问题,其它相关修改可详看链家产品技术团队做的翻译及整理:PHP7.2 版本指南
https://mp.weixin.qq.com/s/60pohj2n7Pxba3G9vY92yg 查看全部
最近升级了PHP版本,从7.1升级到7.2,升级前版本:
PHP 7.1.14 (cli) (built: Feb  2 2018 08:42:59) ( NTS )
Copyright (c) 1997-2018 The PHP Group
Zend Engine v3.1.0, Copyright (c) 1998-2018 Zend Technologies
with Zend OPcache v7.1.14, Copyright (c) 1999-2018, by Zend Technologies
with Xdebug v2.6.0, Copyright (c) 2002-2018, by Derick Rethans
升级后版本:
PHP 7.2.2 (cli) (built: Feb 24 2018 17:51:12) ( ZTS DEBUG )
Copyright (c) 1997-2018 The PHP Group
Zend Engine v3.2.0, Copyright (c) 1998-2018 Zend Technologies
with Zend OPcache v7.2.2, Copyright (c) 1999-2018, by Zend Technologies
升级完成之后发现有几个框架在使用时都出现了问题,主要原因集中在7.2之后废弃了一些功能,下面列出几个常见的问题:

1、each函数已被废弃:

之前版本写法:
<?php
$array = array();
each($array);

// Deprecated: The each() function is deprecated. This message will be suppressed on further calls
在7.2版本中会提示过时,可以使用foreach替代each方法,也可以自己修改each方法替代:
<?php
function func_new_each(&$array){
$res = array();
$key = key($array);
if($key !== null){
next($array);
$res[1] = $res['value'] = $array[$key];
$res[0] = $res['key'] = $key;
}else{
$res = false;
}
return $res;
}

2、当传递一个无效参数时,count()函数将抛出warning警告:

之前版本写法
<?php
count('');

// Warning: count(): Parameter must be an array or an object that implements Countable
在7.2版本中将严格执行类型区分,参数类型不正确,将会出现警告,所以需要在使用count方法时注意参数的值,不过也可以通过自己修改方法来替代(不建议):
<?php
function func_new_count($array_or_countable,$mode = COUNT_NORMAL){
if(is_array($array_or_countable) || is_object($array_or_countable)){
return count($array_or_countable, $mode);
}else{
return 0;
}
}
3、create_function被废弃,可以用匿名函数来代替:

之前版本写法:
<?php
$newfunc = create_function('$a,$b', 'return "ln($a) + ln($b) = " . log($a * $b);');
echo "New anonymous function: $newfunc\n";
echo $newfunc(2, M_E) . "\n";
// outputs
// New anonymous function: lambda_1
// ln(2) + ln(2.718281828459) = 1.6931471805599

// Warning This function has been DEPRECATED as of PHP 7.2.0. Relying on this function is highly discouraged.
在7.2版本中会有警告提示,可修改为匿名函数来替代:
<?php
$newfunc = function ($a,$b){
return "ln($a) + ln($b) = " . log($a * $b);
};
echo $newfunc(2, M_E) . "\n";
以上就是升级之后暂时遇到的几个问题,其它相关修改可详看链家产品技术团队做的翻译及整理:PHP7.2 版本指南
https://mp.weixin.qq.com/s/60pohj2n7Pxba3G9vY92yg

海量数据相似度计算算法:simhash和海明距离

架构思想zkbhj 发表了文章 • 0 个评论 • 95 次浏览 • 2018-09-12 16:04 • 来自相关话题

通过 采集系统 我们采集了大量文本数据,但是文本中有很多重复数据影响我们对于结果的分析。分析前我们需要对这些数据去除重复,如何选择和设计文本的去重算法?常见的有余弦夹角算法、欧式距离、Jaccard相似度、最长公共子串、编辑距离等。这些算法对于待比较的文本数据不多时还比较好用,如果我们的爬虫每天采集的数据以千万计算,我们如何对于这些海量千万级的数据进行高效的合并去重。最简单的做法是拿着待比较的文本和数据库中所有的文本比较一遍如果是重复的数据就标示为重复。看起来很简单,我们来做个测试,就拿最简单的两个数据使用Apache提供的 Levenshtein for 循环100w次计算这两个数据的相似度。代码结果如下:
String s1 = "你妈妈喊你回家吃饭哦,回家罗回家罗" ;
String s2 = "你妈妈叫你回家吃饭啦,回家罗回家罗" ;

long t1 = System.currentTimeMillis();

for (int i = 0; i < 1000000; i++) {
int dis = StringUtils .getLevenshteinDistance(s1, s2);
}

long t2 = System.currentTimeMillis();

System. out .println(" 耗费时间: " + (t2 - t1) + " ms ");耗费时间: 4266 ms

大跌眼镜,居然计算耗费4秒。假设我们一天需要比较100w次,光是比较100w次的数据是否重复就需要4s,就算4s一个文档,单线程一分钟才处理15个文档,一个小时才900个,一天也才21600个文档,这个数字和一天100w相差甚远,需要多少机器和资源才能解决。

为此我们需要一种应对于海量数据场景的去重方案,经过研究发现有种叫 local sensitive hash 局部敏感哈希 的东西,据说这玩意可以把文档降维到hash数字,数字两两计算运算量要小很多。查找很多文档后看到google对于网页去重使用的是simhash,他们每天需要处理的文档在亿级别,大大超过了我们现在文档的水平。既然老大哥也有类似的应用,我们也赶紧尝试下。simhash是由 Charikar 在2002年提出来的,参考 《Similarity estimation techniques from rounding algorithms》 。 介绍下这个算法主要原理,为了便于理解尽量不使用数学公式,分为这几步:
 

1、分词,把需要判断文本分词形成这个文章的特征单词。最后形成去掉噪音词的单词序列并为每个词加上权重,我们假设权重分为5个级别(1~5)。比如:“ 美国“51区”雇员称内部有9架飞碟,曾看见灰色外星人 ” ==> 分词后为 “ 美国(4) 51区(5) 雇员(3) 称(1) 内部(2) 有(1) 9架(3) 飞碟(5) 曾(1) 看见(3) 灰色(4) 外星人(5)”,括号里是代表单词在整个句子里重要程度,数字越大越重要。

2、hash,通过hash算法把每个词变成hash值,比如“美国”通过hash算法计算为 100101,“51区”通过hash算法计算为 101011。这样我们的字符串就变成了一串串数字,还记得文章开头说过的吗,要把文章变为数字计算才能提高相似度计算性能,现在是降维过程进行时。

3、加权,通过 2步骤的hash生成结果,需要按照单词的权重形成加权数字串,比如“美国”的hash值为“100101”,通过加权计算为“4 -4 -4 4 -4 4”;“51区”的hash值为“101011”,通过加权计算为 “ 5 -5 5 -5 5 5”。

4、合并,把上面各个单词算出来的序列值累加,变成只有一个序列串。比如 “美国”的 “4 -4 -4 4 -4 4”,“51区”的 “ 5 -5 5 -5 5 5”, 把每一位进行累加, “4+5 -4+-5 -4+5 4+-5 -4+5 4+5” ==》 “9 -9 1 -1 1 9”。这里作为示例只算了两个单词的,真实计算需要把所有单词的序列串累加。

5、降维,把4步算出来的 “9 -9 1 -1 1 9” 变成 0 1 串,形成我们最终的simhash签名。 如果每一位大于0 记为 1,小于0 记为 0。最后算出结果为:“1 0 1 0 1 1”。

 
整个过程图为:





 
大家可能会有疑问,经过这么多步骤搞这么麻烦,不就是为了得到个 0 1 字符串吗?我直接把这个文本作为字符串输入,用hash函数生成 0 1 值更简单。其实不是这样的,传统hash函数解决的是生成唯一值,比如 md5、hashmap等。md5是用于生成唯一签名串,只要稍微多加一个字符md5的两个数字看起来相差甚远;hashmap也是用于键值对查找,便于快速插入和查找的数据结构。不过我们主要解决的是文本相似度计算,要比较的是两个文章是否相识,当然我们降维生成了hashcode也是用于这个目的。看到这里估计大家就明白了,我们使用的simhash就算把文章中的字符串变成 01 串也还是可以用于计算相似度的,而传统的hashcode却不行。我们可以来做个测试,两个相差只有一个字符的文本串,“你妈妈喊你回家吃饭哦,回家罗回家罗” 和 “你妈妈叫你回家吃饭啦,回家罗回家罗”。

通过simhash计算结果为:

1000010010101101111111100000101011010001001111100001001011001011

1000010010101101011111100000101011010001001111100001101010001011

通过 hashcode计算为:

1111111111111111111111111111111110001000001100110100111011011110

1010010001111111110010110011101

大家可以看得出来,相似的文本只有部分 01 串变化了,而普通的hashcode却不能做到,这个就是局部敏感哈希的魅力。目前Broder提出的shingling算法和Charikar的simhash算法应该算是业界公认比较好的算法。在simhash的发明人Charikar的论文中并没有给出具体的simhash算法和证明,“量子图灵”得出的证明simhash是由随机超平面hash算法演变而来的。

现在通过这样的转换,我们把库里的文本都转换为simhash 代码,并转换为long类型存储,空间大大减少。现在我们虽然解决了空间,但是如何计算两个simhash的相似度呢?难道是比较两个simhash的01有多少个不同吗?对的,其实也就是这样,我们通过海明距离(Hamming distance)就可以计算出两个simhash到底相似不相似。两个simhash对应二进制(01串)取值不同的数量称为这两个simhash的海明距离。举例如下: 10101 和 00110 从第一位开始依次有第一位、第四、第五位不同,则海明距离为3。对于二进制字符串的a和b,海明距离为等于在a XOR b运算结果中1的个数(普遍算法)。

为了高效比较,我们预先加载了库里存在文本并转换为simhash code 存储在内存空间。来一条文本先转换为 simhash code,然后和内存里的simhash code 进行比较,测试100w次计算在100ms。速度大大提升。

未完待续:

1、目前速度提升了但是数据是不断增量的,如果未来数据发展到一个小时100w,按现在一次100ms,一个线程处理一秒钟 10次,一分钟 60 * 10 次,一个小时 60*10 *60 次 = 36000次,一天 60*10*60*24 = 864000次。 我们目标是一天100w次,通过增加两个线程就可以完成。但是如果要一个小时100w次呢?则需要增加30个线程和相应的硬件资源保证速度能够达到,这样成本也上去了。能否有更好的办法,提高我们比较的效率?

2、通过大量测试,simhash用于比较大文本,比如500字以上效果都还蛮好,距离小于3的基本都是相似,误判率也比较低。但是如果我们处理的是微博信息,最多也就140个字,使用simhash的效果并不那么理想。看如下图,在距离为3时是一个比较折中的点,在距离为10时效果已经很差了,不过我们测试短文本很多看起来相似的距离确实为10。如果使用距离为3,短文本大量重复信息不会被过滤,如果使用距离为10,长文本的错误率也非常高,如何解决?




  查看全部
通过 采集系统 我们采集了大量文本数据,但是文本中有很多重复数据影响我们对于结果的分析。分析前我们需要对这些数据去除重复,如何选择和设计文本的去重算法?常见的有余弦夹角算法、欧式距离、Jaccard相似度、最长公共子串、编辑距离等。这些算法对于待比较的文本数据不多时还比较好用,如果我们的爬虫每天采集的数据以千万计算,我们如何对于这些海量千万级的数据进行高效的合并去重。最简单的做法是拿着待比较的文本和数据库中所有的文本比较一遍如果是重复的数据就标示为重复。看起来很简单,我们来做个测试,就拿最简单的两个数据使用Apache提供的 Levenshtein for 循环100w次计算这两个数据的相似度。代码结果如下:
String s1 = "你妈妈喊你回家吃饭哦,回家罗回家罗" ;
String s2 = "你妈妈叫你回家吃饭啦,回家罗回家罗" ;

long t1 = System.currentTimeMillis();

for (int i = 0; i < 1000000; i++) {
int dis = StringUtils .getLevenshteinDistance(s1, s2);
}

long t2 = System.currentTimeMillis();

System. out .println(" 耗费时间: " + (t2 - t1) + " ms ");
耗费时间: 4266 ms

大跌眼镜,居然计算耗费4秒。假设我们一天需要比较100w次,光是比较100w次的数据是否重复就需要4s,就算4s一个文档,单线程一分钟才处理15个文档,一个小时才900个,一天也才21600个文档,这个数字和一天100w相差甚远,需要多少机器和资源才能解决。

为此我们需要一种应对于海量数据场景的去重方案,经过研究发现有种叫 local sensitive hash 局部敏感哈希 的东西,据说这玩意可以把文档降维到hash数字,数字两两计算运算量要小很多。查找很多文档后看到google对于网页去重使用的是simhash,他们每天需要处理的文档在亿级别,大大超过了我们现在文档的水平。既然老大哥也有类似的应用,我们也赶紧尝试下。simhash是由 Charikar 在2002年提出来的,参考 《Similarity estimation techniques from rounding algorithms》 。 介绍下这个算法主要原理,为了便于理解尽量不使用数学公式,分为这几步:
 


1、分词,把需要判断文本分词形成这个文章的特征单词。最后形成去掉噪音词的单词序列并为每个词加上权重,我们假设权重分为5个级别(1~5)。比如:“ 美国“51区”雇员称内部有9架飞碟,曾看见灰色外星人 ” ==> 分词后为 “ 美国(4) 51区(5) 雇员(3) 称(1) 内部(2) 有(1) 9架(3) 飞碟(5) 曾(1) 看见(3) 灰色(4) 外星人(5)”,括号里是代表单词在整个句子里重要程度,数字越大越重要。

2、hash,通过hash算法把每个词变成hash值,比如“美国”通过hash算法计算为 100101,“51区”通过hash算法计算为 101011。这样我们的字符串就变成了一串串数字,还记得文章开头说过的吗,要把文章变为数字计算才能提高相似度计算性能,现在是降维过程进行时。

3、加权,通过 2步骤的hash生成结果,需要按照单词的权重形成加权数字串,比如“美国”的hash值为“100101”,通过加权计算为“4 -4 -4 4 -4 4”;“51区”的hash值为“101011”,通过加权计算为 “ 5 -5 5 -5 5 5”。

4、合并,把上面各个单词算出来的序列值累加,变成只有一个序列串。比如 “美国”的 “4 -4 -4 4 -4 4”,“51区”的 “ 5 -5 5 -5 5 5”, 把每一位进行累加, “4+5 -4+-5 -4+5 4+-5 -4+5 4+5” ==》 “9 -9 1 -1 1 9”。这里作为示例只算了两个单词的,真实计算需要把所有单词的序列串累加。

5、降维,把4步算出来的 “9 -9 1 -1 1 9” 变成 0 1 串,形成我们最终的simhash签名。 如果每一位大于0 记为 1,小于0 记为 0。最后算出结果为:“1 0 1 0 1 1”。


 
整个过程图为:

simhash.png

 
大家可能会有疑问,经过这么多步骤搞这么麻烦,不就是为了得到个 0 1 字符串吗?我直接把这个文本作为字符串输入,用hash函数生成 0 1 值更简单。其实不是这样的,传统hash函数解决的是生成唯一值,比如 md5、hashmap等。md5是用于生成唯一签名串,只要稍微多加一个字符md5的两个数字看起来相差甚远;hashmap也是用于键值对查找,便于快速插入和查找的数据结构。不过我们主要解决的是文本相似度计算,要比较的是两个文章是否相识,当然我们降维生成了hashcode也是用于这个目的。看到这里估计大家就明白了,我们使用的simhash就算把文章中的字符串变成 01 串也还是可以用于计算相似度的,而传统的hashcode却不行。我们可以来做个测试,两个相差只有一个字符的文本串,“你妈妈喊你回家吃饭哦,回家罗回家罗” 和 “你妈妈叫你回家吃饭啦,回家罗回家罗”。

通过simhash计算结果为:

1000010010101101111111100000101011010001001111100001001011001011

1000010010101101011111100000101011010001001111100001101010001011

通过 hashcode计算为:

1111111111111111111111111111111110001000001100110100111011011110

1010010001111111110010110011101

大家可以看得出来,相似的文本只有部分 01 串变化了,而普通的hashcode却不能做到,这个就是局部敏感哈希的魅力。目前Broder提出的shingling算法和Charikar的simhash算法应该算是业界公认比较好的算法。在simhash的发明人Charikar的论文中并没有给出具体的simhash算法和证明,“量子图灵”得出的证明simhash是由随机超平面hash算法演变而来的。

现在通过这样的转换,我们把库里的文本都转换为simhash 代码,并转换为long类型存储,空间大大减少。现在我们虽然解决了空间,但是如何计算两个simhash的相似度呢?难道是比较两个simhash的01有多少个不同吗?对的,其实也就是这样,我们通过海明距离(Hamming distance)就可以计算出两个simhash到底相似不相似。两个simhash对应二进制(01串)取值不同的数量称为这两个simhash的海明距离。举例如下: 10101 和 00110 从第一位开始依次有第一位、第四、第五位不同,则海明距离为3。对于二进制字符串的a和b,海明距离为等于在a XOR b运算结果中1的个数(普遍算法)。

为了高效比较,我们预先加载了库里存在文本并转换为simhash code 存储在内存空间。来一条文本先转换为 simhash code,然后和内存里的simhash code 进行比较,测试100w次计算在100ms。速度大大提升。

未完待续:

1、目前速度提升了但是数据是不断增量的,如果未来数据发展到一个小时100w,按现在一次100ms,一个线程处理一秒钟 10次,一分钟 60 * 10 次,一个小时 60*10 *60 次 = 36000次,一天 60*10*60*24 = 864000次。 我们目标是一天100w次,通过增加两个线程就可以完成。但是如果要一个小时100w次呢?则需要增加30个线程和相应的硬件资源保证速度能够达到,这样成本也上去了。能否有更好的办法,提高我们比较的效率?

2、通过大量测试,simhash用于比较大文本,比如500字以上效果都还蛮好,距离小于3的基本都是相似,误判率也比较低。但是如果我们处理的是微博信息,最多也就140个字,使用simhash的效果并不那么理想。看如下图,在距离为3时是一个比较折中的点,在距离为10时效果已经很差了,不过我们测试短文本很多看起来相似的距离确实为10。如果使用距离为3,短文本大量重复信息不会被过滤,如果使用距离为10,长文本的错误率也非常高,如何解决?
simhash2.png

 

PHP中如何识别图片是否翻转并矫正?

回复

PHPzkbhj 回复了问题 • 1 人关注 • 1 个回复 • 123 次浏览 • 2018-09-11 17:57 • 来自相关话题