Loading [MathJax]/jax/element/mml/optable/BasicLatin.js
  • 中国精品科技期刊
  • CCF推荐A类中文期刊
  • 计算领域高质量科技期刊T1类
高级检索

WebAssembly安全综述

庄骏杰, 胡霜, 华保健, 汪炀, 潘志中

庄骏杰, 胡霜, 华保健, 汪炀, 潘志中. WebAssembly安全综述[J]. 计算机研究与发展, 2024, 61(12): 3027-3053. DOI: 10.7544/issn1000-1239.202330049
引用本文: 庄骏杰, 胡霜, 华保健, 汪炀, 潘志中. WebAssembly安全综述[J]. 计算机研究与发展, 2024, 61(12): 3027-3053. DOI: 10.7544/issn1000-1239.202330049
Zhuang Junjie, Hu Shuang, Hua Baojian, Wang Yang, Pan Zhizhong. Survey of WebAssembly Security[J]. Journal of Computer Research and Development, 2024, 61(12): 3027-3053. DOI: 10.7544/issn1000-1239.202330049
Citation: Zhuang Junjie, Hu Shuang, Hua Baojian, Wang Yang, Pan Zhizhong. Survey of WebAssembly Security[J]. Journal of Computer Research and Development, 2024, 61(12): 3027-3053. DOI: 10.7544/issn1000-1239.202330049
庄骏杰, 胡霜, 华保健, 汪炀, 潘志中. WebAssembly安全综述[J]. 计算机研究与发展, 2024, 61(12): 3027-3053. CSTR: 32373.14.issn1000-1239.202330049
引用本文: 庄骏杰, 胡霜, 华保健, 汪炀, 潘志中. WebAssembly安全综述[J]. 计算机研究与发展, 2024, 61(12): 3027-3053. CSTR: 32373.14.issn1000-1239.202330049
Zhuang Junjie, Hu Shuang, Hua Baojian, Wang Yang, Pan Zhizhong. Survey of WebAssembly Security[J]. Journal of Computer Research and Development, 2024, 61(12): 3027-3053. CSTR: 32373.14.issn1000-1239.202330049
Citation: Zhuang Junjie, Hu Shuang, Hua Baojian, Wang Yang, Pan Zhizhong. Survey of WebAssembly Security[J]. Journal of Computer Research and Development, 2024, 61(12): 3027-3053. CSTR: 32373.14.issn1000-1239.202330049

WebAssembly安全综述

基金项目: 国家自然科学基金项目(62072427,12227901);中国科学院稳定支持基础研究领域青年团队计划项目(YSBR-005);中国科学技术大学学术带头人培养项目
详细信息
    作者简介:

    庄骏杰: 1998年生. 硕士研究生. 主要研究方向为程序设计语言、网络与信息安全

    胡霜: 1995年生. 硕士研究生. 主要研究方向为程序设计语言与编译器

    华保健: 1979年生. 博士,讲师. CCF会员. 主要研究方向为程序设计语言、网络与信息安全

    汪炀: 1980年生. 博士,副教授. CCF高级会员. 主要研究方向为时空数据挖掘与交叉研究、无线传感网与车联网、分布式系统

    潘志中: 1988年生. 硕士. 主要研究方向为程序语言安全、区块链安全

  • 中图分类号: TP312

Survey of WebAssembly Security

Funds: This work was supported by the National Natural Science Foundation of China (62072427, 12227901), the Project of Stable Support for Youth Team in Basic Research Field, Chinese Academy of Sciences (YSBR-005), and the Academic Leaders Cultivation Program, University of Science and Technology of China.
More Information
    Author Bio:

    Zhuang Junjie: born in 1998. Master candidate. His main research interests include programming languages, and cyber and information security

    Hu Shuang: born in 1995. Master candidate. Her main research interest includes programming language and compiler

    Hua Baojian: born in 1979. PhD, lecturer. Member of CCF. His main research interests include programming languages and cyber and information security. (bjhua@ustc.edu.cn)

    Wang Yang: born in 1980. PhD, associate professor. Senior member of CCF. His main research interests include spatiotemporal data mining and its interdisciplinary studies, wireless sensor network and vehicular network, and distributed systems. (angyan@ustc.edu.cn)

    Pan Zhizhong: born in 1988. Master. His main research interests include programming languages security and blockchain security

  • 摘要:

    WebAssembly是一种新兴的二进制指令集体系结构与代码分发格式,旨在为高级程序语言提供统一且架构无关的编译目标. 由于其安全、高效与可移植等先进特性,WebAssembly在Web领域与非Web领域均得到了广泛应用,正在成为最有前景的跨平台公共语言标准之一. 尽管WebAssembly提供了多种先进特性以保证安全性,然而,已有研究表明,WebAssembly仍然存在特有的攻击面从而导致安全问题,这些安全问题直接影响到基于WebAssembly的整个软件系统生态. 因此,对WebAssembly安全问题的产生机理、现有解决方案以及亟待解决的科学问题展开系统研究尤为重要. 基于WebAssembly安全研究领域已经公开发表的42篇研究论文,对WebAssembly安全的相关研究进行了系统研究、分析、归纳和总结:首先,研究分析了WebAssembly的核心安全特性,并在此基础上首次提出了WebAssembly的4层安全威胁模型,包括高级语言支持、编译工具链、二进制表示和语言虚拟机,并对每一层的安全威胁和攻击面进行了详细讨论;其次,提出了WebAssembly安全研究的分类学,将已有研究划分为安全实证研究、漏洞检测与利用、安全增强、形式语义与程序验证4个热点研究方向,并对这4个方向分别进行了综述、分析和总结;最后,指出了该领域待解决的科学问题,并展望了5个潜在的研究方向.

    Abstract:

    WebAssembly is an emerging binary instruction set architecture and code distribution format, providing a unified compiling target for high-level programming languages. Due to its design advantages such as efficiency, security and portability, WebAssembly has already been widely used in the Web and non-Web scenarios, and it is becoming one of the most promising platform-independent language runtimes. Although WebAssembly provides a variety of advanced features to guarantee its security, existing studies have demonstrated that WebAssembly still has unique attack surfaces leading to serious security issues. These security issues pose challenges to the security of whole ecosystems based on WebAssembly. Therefore, it is critical to study the security issues of WebAssembly and their mitigations. To the best of our knowledge, we present the first study of WebAssembly security, based on 42 published research papers in this area. First, we systematically analyze and summarize key security features of WebAssembly. Second, we propose the first four-layer threat model for WebAssembly: threats from high-level programming languages, compilation toolchains, binary files, and WebAssembly virtual machines. Third, we propose a taxonomy to classify current research efforts into four categories: empirical security study, vulnerability detection and exploitation, security enhancements, and formal semantics and verifications. Finally, we point out potential challenges to be addressed in this field, as well as five future research directions to be explored.

  • 传统协同过滤推荐算法[1-2]作为大数据时代解决信息过载问题的重要手段,在餐厅推荐[3]、景点推荐[4]、广告推荐[5]等领域得到了广泛的应用. 协同过滤算法的主要思想是基于用户反馈学习用户偏好,可以为用户提供个性化服务,提升用户满意度与平台商业收入. 然而当用户反馈数据非常稀疏时,协同过滤算法往往不能有效捕捉用户的偏好,数据稀疏性将导致推荐算法产生严重过拟合,影响推荐算法的性能.

    针对存在2种评分格式的推荐场景,相对于5分制数值评分,用户更倾向于进行简单的1,0二元(喜欢和不喜欢)评分,因此除目标域稀疏的5分制数值评分外,该推荐场景往往含有辅助域上相对较丰富的二元评分. 此处,目标域指的是运行推荐算法的数据集,往往可用于分析的评分数据比较匮乏. 辅助域指的是与目标域有一定关联的其他数据集,相对于目标域通常具有更为丰富的评分数据. 在迁移学习框架下,辅助域也被称为源域(source domain). 针对该类推荐场景,近年来部分研究者提出了一种跨评分的推荐方法[6-10],通过迁移辅助域上挖掘到的有价值的知识到目标域,提升目标域上的推荐性能. 为与其他推荐模式相区分,本文称之为跨评分协同过滤范式,定义如下.

    定义1. 跨评分协同过滤范式. 假设辅助域包含较丰富的0,1评分,目标域包含稀疏的1~5评分,跨评分协同过滤范式是指将辅助域信息迁移到目标域来提升目标域推荐性能的推荐模式.

    针对跨评分协同过滤范式,Pan等人[6]提出基于联合分解的迁移模型(TCF),该模型假定目标域和辅助域共享同一用户隐特征空间和项目隐特征空间,但具有不同的簇级评分模式,通过联合分解的方式实现重要知识由辅助域向目标域的迁移. 在TCF基础上,针对数据异构造成用户隐向量的变化,Pan等人[7]提出基于联合分解的交互丰富迁移模型(iTCF),通过共享预测性能来实现辅助域和目标域用户隐特征的交互. iTCF是基于联合方式的迁移学习算法,该算法包含2个松耦合的矩阵分解任务. 为更充分地进行知识迁移,Pan等人[8]进一步提出基于混合分解的迁移模型(TMF),该模型结合辅助域中数据提取用户的喜欢偏好和不喜欢偏好,并合并2种偏好辅助目标域矩阵分解,这种方式将原本2个松耦合的矩阵分解之间的联系变得更加密切,提高了模型的推荐性能. Zhang等人[9]和Jiang等人[10]均对三因子矩阵分解中的簇级评分模式进一步分解,捕获不同域的共享评分模式,同时分离领域特有的评分模式. 特别地,Zhang等人[9]提出用于协同过滤的基于多源异构反馈的增强知识转移模型(EKT),通过提取目标域和辅助域中用户和项目的几何结构图信息,来改善2个域的隐向量的学习效果. Jiang等人[10]则提出深度低秩稀疏联合分解模型(DLSCF),该模型考虑项目类型的树状层次结构,以多层三因子矩阵分解的方式建模项目的隐式层次结构.

    然而,以往跨评分协同过滤范式往往假设推荐系统中的所有区域数值评分均较为稀疏,对不同区域采取一致的评分预测策略. 实际上,尽管目标域整体数值评分较为稀疏,但是仍然有部分活跃用户在部分热门项目上评分比较密集. 例如,在Movielens数据集上,我们可以容易地找出一个100活跃用户和200热门影片组成的评分子集,该子集具有相对较高的评分密度. 以往跨评分协同过滤范式在知识迁移的过程中忽视了评分密度对用户和项目隐向量求解精度的影响,导致评分稀疏区域评分预测不够准确. 考虑到活跃用户和热门项目所在区域上的2种评分均较为密集,从该区域相关评分数据中挖掘有价值的知识,并迁移到评分非密集区域可以有效提升模型对目标域整体的评分预测性能,尤其是针对评分非密集区域的评分预测性能. 因此,基于迁移学习思想,本文提出一种跨区域跨评分协同过滤推荐算法(a cross-region and cross-rating collaborative filtering recommendation algorithm,CRCRCF). 首先,基于目标域评分个数将全体用户划分为活跃用户和非活跃用户,将全部项目划分为热门项目和非热门项目. 为了更好地进行用户和项目表征,利用图卷积矩阵补全(graph convolutional matrix completion,GC-MC)算法[11]提取目标域活跃用户和热门项目,以及辅助域中全体用户和项目的隐向量. 由于目标域活跃用户和热门项目对应的评分密集区域以及辅助域中评分均较为丰富,所提取的隐向量相对较为准确. 其次,针对活跃用户和热门项目,构建基于自教学习(self-taught learning)[12]的深度回归网络分别学习目标域和辅助域上2种评分对应的用户隐向量和项目隐向量的映射关系. 然后,将活跃用户和热门项目的隐向量的映射关系泛化到目标域非活跃用户和非热门项目上,利用非活跃用户和非热门项目在辅助域上相对准确的隐向量推导其在目标域上的隐向量,依次实现了跨区域映射关系迁移和跨评分的隐向量信息迁移. 最后,以求得的非活跃用户和非热门项目在目标域上的隐向量为约束,提出受限图卷积矩阵补全模型,并给出相应推荐结果.

    为了避免本文提出的跨区域推荐与传统跨域推荐混淆,将二者定义为:

    定义2. 跨区域推荐. 跨区域推荐是指将活跃用户和热门项目对应的评分密集区域的信息迁移到非密集区域,来提升评分非密集区域推荐性能的推荐模式.

    定义3. 跨域推荐. 假设辅助域与目标域物品种类不一致,跨域推荐是指将评分数据较丰富的辅助域信息迁移到评分数据较匮乏的目标域来提升目标域推荐性能的推荐模式.

    本文所提出的“跨区域”是指在不同评分密度的区域之间实现知识迁移,是不同于传统跨域推荐的新范式. 在MovieLens10M和Netflix数据集上的广泛对比实验验证了本文算法在4种不同测试指标上较其他多种最先进的对比方法具有明显优势.

    本文的主要贡献有3点:

    1)提出跨区域推荐范式,可以进行细粒度的精准推荐;

    2)提出基于自教学习的深度回归网络学习活跃用户和热门项目在目标域和辅助域上对应的隐向量的映射关系,可充分利用非活跃用户和非热门项目相关的大量无监督数据提高映射关系建模的准确性;

    3)提出受限图卷积矩阵补全模型,以有效融合目标域稀疏数值评分和辅助域二元评分,有效避免迁移学习中的负迁移现象.

    跨域推荐算法基于迁移学习或者多任务学习技术,有效利用辅助域上重要信息缓解目标域数据稀疏性难题,通常根据所讨论场景中用户的重叠情况被分为3类:完全不重叠、部分重叠和完全重叠.

    针对完全不重叠情况,Li等人[13]提出码本迁移模型(CBT),该模型利用辅助域的丰富评分信息提取簇级评分模式,即密码本,并将密码本迁移到目标域上来提升目标域矩阵分解的准确性. 在此基础上,Li等人[14]又提出评分矩阵生成模型(RMGM),通过多任务学习方法提高推荐性能. Zhang等人[15]提出结合标签系统语义相关性的跨域推荐模型(SCT),利用目标域和辅助域标签语义信息的相似关系构建连接2个平台用户或项目的桥梁,实现辅助域知识向目标域的迁移. Li等人[16]提出基于对抗学习深度稀疏自编码器的跨域推荐模型(DSAP-AL),利用对抗生成网络对齐目标域和辅助域的用户和项目的潜在因子空间,并结合深度稀疏自编码器实现知识迁移.

    针对部分重叠情况,Jiang 等人[17]提出半监督迁移学习模型(XPTRANS). Zhang等人[18]提出基于核诱导知识迁移的跨域推荐模型(KerKT). Zhu等人[19]提出结合图和注意力机制的双向迁移跨域推荐模型(GA-DTCDR),利用异构图模型捕获用户和项目的特征,并提出注意力机制来结合共享用户的特征,实现用户特征的双向迁移. Li等人[20]进一步提出基于对偶度量学习的跨域推荐模型(DML),通过将度量学习引入对偶学习减轻了对重叠用户数目的要求.

    针对用户完全重叠情况的研究最为广泛,目前该方面的研究通常可以分为信息集成和知识集成2种. 在信息集成方面,Berkovsky等人[21]提出基于邻域的跨域推荐模型(N-CDCF),该模型是基于邻域的协同过滤模型(N-CF)[22]的跨域版本. 假定用户在不同域上共享潜在因子,Singh等人[23]提出联合矩阵分解模型(CMF). 这些模型通过拼接目标域和辅助域评分矩阵来缓解目标域数据稀疏问题. 针对知识集成,Hu等人[24]提出跨域三元分解模型(CDTF)来捕捉用户、项目和域之间的三元关系,并基于张量分解实现跨域推荐. Loni等人[25]提出跨域因子分解机模型(CDFM),该模型从辅助域中的用户评分信息中提取用户特征并将其转移到目标域,以提升目标域上的推荐性能. Yuan等人[26]提出深度域适应跨域推荐模型(DARec)来提取和迁移潜在的评分模式. 通过进一步假设存在一些辅助域与目标域共享项目,Yu等人[27-28]提出双侧跨域协同过滤算法,分别提取域无关特征和域依赖特征并转移到目标域,以提高目标域推荐性能. Pan等人[29]提出坐标系统迁移模型(CST),分别从用户辅助域和项目辅助域中提取用户和项目隐向量,并将它们迁移到目标域以辅助目标域进行矩阵分解. Yu等人[30]提出具有隐私保护功能的跨域推荐模型(PPCDHWRec),仅迁移用户在辅助域的域依赖和域无关特征,保留项目的隐特征,提升了目标域推荐系统的性能,且实现了辅助域原始评分隐私保护的效果.

    Pan等人[6]提出TCF算法,该算法针对目标域辅助域的评分矩阵进行如下联合分解,以缓解目标域数据的稀疏性难题.

    min (1)

    其中U表示共享的用户隐向量矩阵,V表示共享的项目隐向量矩阵, {\boldsymbol{B}} {{\tilde {\boldsymbol B}}} 分别表示目标域和辅助域的数据依赖的簇级评分模式. 根据用户和项目隐向量约束条件的不同,TCF可以分为2种变体,分别是联合矩阵三分解模型(CMTF)和联合奇异值分解模型(CSVD),其中CSVD要求UV是正交矩阵,即,具有更好的推荐性能.

    考虑到TCF算法效率较低以及目标域和辅助域数据异构会造成用户隐向量发生变化,Pan等人[7]提出iTCF算法,与TCF算法不同,iTCF算法在评分矩阵分解过程中不再考虑簇级评分模式,直接将评分矩阵分解为用户隐向量矩阵和项目隐向量矩阵. 该算法通过求解如下优化问题实现辅助域和目标域用户隐特征的交互:

    \mathop {\min }\limits_{{\boldsymbol U},{\boldsymbol W},{\boldsymbol V}} \mathcal{F}\left( {{{\boldsymbol R}}\thicksim {{\boldsymbol U}}{{{\boldsymbol V}}^{\rm T}}} \right)+\lambda \mathcal{F}\left( {{\tilde{\boldsymbol R}}\thicksim {{\boldsymbol W}}{{{\boldsymbol V}}^{\rm T}}} \right),\;\;{\rm{s.t.}}{\boldsymbol E} = {\tilde{\boldsymbol E}}\text{,} (2)

    其中UW分别表示目标域和辅助域的用户隐向量矩阵,V表示共享的项目隐向量矩阵,{\boldsymbol E}{\tilde{\boldsymbol E}}分别表示预测模型在2种评分上的误差.

    尽管iTCF考虑到数据异构造成的用户隐向量的变化,但作为一种基于联合方式的迁移学习算法,该算法包含2个松耦合的矩阵分解任务,仍不能充分利用辅助域评分数据. Pan等人[8]进一步提出TMF算法,该算法是一种混合迁移学习策略,包含联合的(collective)基于特征的迁移和综合的(integrative)基于实例的迁移2种迁移学习方式. 通过在目标域的分解过程中考虑辅助域提取的用户喜欢和不喜欢偏好,加强了2个松耦合矩阵分解之间的联系,可以更充分地进行知识迁移.

    考虑到不同域的评分模式既包含不同域之间共享的评分模式,又包含各领域特有的评分模式,Zhang等人[9]和Jiang等人[10]对不同域的评分模式进一步分解,以迁移不同域中共享的评分模式. Zhang等人[9]的方法中目标域和辅助域的簇级评分模式 {{\boldsymbol{B}}_{\rm t} } {{\boldsymbol{B}}_{\rm s} } 分别被分解为

    {{\boldsymbol{B}}_{\rm t}} = [{{\boldsymbol S}},{{{\boldsymbol S}}_{\rm t}}],{\text{ }}{{\boldsymbol{B}}_{\rm s}} = [{{\boldsymbol S}},{{{\boldsymbol S}}_{\rm a}}] \text{,} (3)

    其中 {{\boldsymbol S}} 表示共享的评分模式矩阵, {{{\boldsymbol S}}_{\rm t}} {{{\boldsymbol S}}_{\rm a}} 分别表示目标域和辅助域特有的评分模型矩阵. Jiang等人[10]的方法中目标域和辅助域的簇级评分模式 {\boldsymbol{B}} {{\tilde {\boldsymbol B}}} 分别被分解为

    {\boldsymbol{B}} = {{\boldsymbol D}}+{\boldsymbol E},\;\;{\tilde{\boldsymbol B}} = {{\boldsymbol D}}+{\tilde{\boldsymbol E}} \text{,} (4)

    其中D表示共享的低秩评分模式部分,{\boldsymbol E}{\tilde{\boldsymbol E}}分别表示目标域和辅助域特有的评分模式部分. 在此基础上,Zhang等人[9]提出了EKT算法,通过用户和项目评分相关的几何结构信息构建正则项,以此约束矩阵分解过程中用户和项目隐向量的学习,避免了迁移过程中的负迁移和迁移不足问题. Jiang等人[10]提出了DLSCF算法,该算法以多层的方式对评分矩阵进行分解来捕获项目的潜在类别和潜在子类别之间的层次关系,多层分解的方式为:

    {{\boldsymbol R}} = {{{\boldsymbol U}}_1}{{\boldsymbol{B}}_1}{{{\boldsymbol V}}_1},{\text{ }}{{\boldsymbol{B}}_1} = {{{\boldsymbol U}}_2}{{\boldsymbol{B}}_2}{{{\boldsymbol V}}_2},{\text{ }} … ,{\text{ }}{{\boldsymbol{B}}_{l - 1}} = {{{\boldsymbol U}}_l}{{\boldsymbol{B}}_l}{{{\boldsymbol V}}_l} \text{,} (5)

    其中l表示多层矩阵分解的层数.

    上述跨评分协同过滤算法将辅助域重要知识迁移到目标域,以有效提升目标域上推荐结果的准确性. 但是上述方法默认目标域不同区域具有相同的评分密度,对不同区域采取一致的评分预测策略,忽视了评分密度对用户和项目隐向量求解精度的影响,导致评分稀疏区域评分预测不够准确. 为克服这一不足,本文将在第2节中提出CRCRCF模型,相对于传统跨评分协同过滤范式,该算法不仅能有效挖掘辅助域的重要知识,而且可以挖掘目标域中评分密集区域的重要知识,可以进一步提升评分稀疏区域的评分预测精度.

    传统跨评分协同过滤范式往往假设推荐系统中的所有用户和所有项目都具有稀疏的数值评分,对全体用户和全体项目同等看待. 该范式将辅助域1,0评分信息中挖掘到的重要知识无差别地迁移到1~5数值评分组成的目标域,以提升目标域上推荐算法的性能. 然而,实际上,尽管目标域整体数值评分较为稀疏,但是仍然有部分活跃用户在部分热门项目上具有较高的评分密度. 如图1所示,如果基于目标域评分个数将用户进一步划分为活跃用户和非活跃用户,将项目进一步划分为热门项目和非热门项目,则abcd这4个区域的1~5数值评分密度满足 density(a) > density(b) > density(d) density(a) > density(c) >density (d) ,且 density(b) density(c) 没有明确的大小关系.

    图  1  目标域用户和项目的划分
    Figure  1.  Division of users and items in the target domain

    矩阵评分密度的定义有:

    定义4. 矩阵评分密度. 设矩阵A的大小为 m \times n ,矩阵中评分个数为s,则评分密度 density({\boldsymbol{A}}) = s/m \times n .

    很明显,目标域中不同的区域具有不同的数值评分密度,高密度区域反馈信息较丰富,对辅助域信息的依赖较小,低密度区域反馈信息较匮乏,对辅助域信息的依赖较大. 因此,应该有针对性地设计辅助域到目标域的知识迁移策略,以有效提升各区域上评分预测的准确性. 为此,本文提出了CRCRCF算法,该算法相对于传统跨评分协同过滤范式将有望拥有更好的推荐性能,其模型结构如图2所示. 首先,图2(a)利用图卷积矩阵补全算法(GC-MC)提取目标域活跃用户和热门项目,以及辅助域中全体用户和项目的隐向量. 其次,图2(b)针对活跃用户和热门项目,构建基于自教学习的深度回归网络(STLDR),分别学习目标域和辅助域上2种评分对应的用户隐向量和项目隐向量的映射关系. 然后,图2(c)将活跃用户和热门项目的隐向量的映射关系泛化到目标域非活跃用户和非热门项目上,利用非活跃用户和非热门项目在辅助域上相对准确的隐向量推导其在目标域上的隐向量,依次实现了跨区域映射关系迁移和跨评分隐向量信息迁移. 最后,图2(d)以求得的非活跃用户和非热门项目在目标域上的隐向量为约束,提出受限图卷积矩阵补全模型(restricted-GC-MC),求解用户和商品最终的隐向量,并对评分进行预测,实现了信息融合. 本文所提出的CRCRCF是一种迁移学习算法. 迁移学习算法通常包括“迁移什么”(what to transfer)与“如何迁移”(how to transfer)2个核心问题. 其中,图2(b)(c)可以看作是“迁移什么”模块,对应2.4节内容,图2(b)求得了映射关系这一可迁移量,图2(c)求得了利用映射关系得到的目标域隐向量这一可迁移量;图2(d)可以看作是“如何迁移”模块,对应2.5节内容,通过自适应的方式实现了迁移的知识与目标域信息的融合.

    图  2  CRCRCF模型结构图
    Figure  2.  Structure diagram of CRCRCF model

    本节基于用户和项目的评分个数将用户和项目划分为活跃用户和非活跃用户、热门项目和非热门项目,以更有针对性地推荐. 相关定义有:

    定义5. 活跃用户和非活跃用户. 对于任意一个用户 u \in U = \{ {u_1},{u_2}, … ,{u_m}\} ,令 {d_u} 表示目标域用户 u 的评分个数(即用户 u 评价的所有项目的个数). 将用户按照评分个数由大到小排序,取前 {\mu _1} 的用户作为活跃用户,剩下的用户作为非活跃用户. 其中 {\mu _1} 是一个预先设定的百分比参数,称为用户活跃度阈值, {\mu _1} 的最优值通过实验来确定.

    定义6. 热门项目和非热门项目. 对于任意一个项目 i \in I = \{ {i_1},{i_2}, … ,{i_n}\} ,令 {d_i} 表示目标域项目的评分个数(即评价过项目i的所有用户的个数). 将项目按照评分个数由大到小排序,取前 {\mu _2} 的项目作为热门项目,剩下项目作为非热门项目. 其中 {\mu _2} 称为项目热门度阈值.

    由定义5和定义6可以看出,活跃用户和热门项目的概念是相对概念,不同的阈值决定不同的活跃用户和热门项目集合.

    本文的推荐场景如图3所示, {{{\boldsymbol R}}^{(5)}} 为目标域数据,是5分制(1~5分)评分矩阵, {{{\boldsymbol R}}^{(2)}} 为辅助域数据,是二元(1/0,即喜欢/不喜欢)评分矩阵, {{{\boldsymbol R}}^{(5)}} {{{\boldsymbol R}}^{(2)}} 共享相同的用户集合 U 和项目集合 I . 在图3中,为了便于观察 {{{\boldsymbol R}}^{(5)}} {{{\boldsymbol R}}^{(2)}} ,我们用前后2个切片对其进行分别表示. 在 {{{\boldsymbol R}}^{(5)}} {U_{\rm a}} = \{ {u_1},{u_2}, … ,{u_{{m_1}}}\} {U_{\rm ina}} = \{ {u_{{m_1}+1}},{u_{{m_1}+2}} ,… ,{u_m}\} 分别表示活跃用户和非活跃用户集合, {I_{\rm p}} = \{ {i_1},{i_2}, … ,{i_{{n_1}}}\} {I_{\rm unp}} = \{ {i_{{n_1}+1}},{i_{{n_1}+2}}, … ,{i_n}\} 分别表示热门项目和非热门项目集合. 所以 {a^{(i)}},{b^{(i)}},{c^{(i)}},{d^{(i)}} (i=5,2)分别表示目标域和辅助域上由活跃用户和热门项目、活跃用户和非热门项目、非活跃用户和热门项目、非活跃用户和非热门项目构成的评分区域.

    图  3  跨区域跨评分推荐场景
    Figure  3.  The cross-region cross-rating recommendation scenario

    通常活跃用户相对于非活跃用户会提供更多的评分,热门项目相对于非热门项目会获得更多的评分,因此, density({a^{(i)}}) 比较高,且 density({d}^{(i)}) <density({b}^{(i)} 或{c}^{(i)}) < density({a}^{(i)}) ,注意 density({b^{(i)}}) density({c^{(i)}}) 通常不存在明显的大小关系,其中i=5,2. 此外,相对于较为复杂的数值评分,全体用户往往更倾向进行1,0二元评分,因此, density({{{\boldsymbol R}}^{(5)}}) < density({{{\boldsymbol R}}^{(2)}}) .

    本文所提CRCRCF模型的目标是充分挖掘辅助域较丰富的二元评分和目标域评分密集区域较为丰富的数值评分,针对目标域不同区域制定个性化的知识迁移策略以生成更为准确的推荐.

    图卷积矩阵补全模型GC-MC被用来提取目标域用户和项目隐向量特征. 相较于传统协同过滤算法,GC-MC可以更为精准地进行用户和项目表征[11]. 值得注意的是,我们利用整体的评分矩阵 {{{\boldsymbol R}}^{(5)}} 对GC-MC进行训练,而不是仅利用活跃用户和热门项目关联的区域 {a^{(5)}} 所对应的评分子矩阵 {{\boldsymbol R}}({a^{(5)}}) 进行训练. 由于 {{{\boldsymbol R}}^{(5)}} {{\boldsymbol R}}({a^{(5)}}) 具有更多的评分信息,因此使用整体的评分矩阵 {{{\boldsymbol R}}^{(5)}} 训练GC-MC可以获得更为精确的隐向量特征.

    设用户-商品二部图为 {G^{(5)}} = ({\mathcal{W}^{(5)}},{\mathcal{E}^{(5)}}) ,其中, {\mathcal{W}^{(5)}} = U \cup I 为用户和项目节点集合, {\mathcal{E}^{(5)}} = \big\{ (u,r_{ui}^{(5)},i)|u,i \in {\mathcal{W}^{(5)}}, r_{ui}^{(5)} \in \{ 1,2,3,4,5\} \big\} 为边集合. 图中节点的初始特征使用one-hot编码表示,全体用户和全体项目节点的初始特征矩阵分别为{{\boldsymbol X}}_U^{(5)}{{\boldsymbol X}}_I^{(5)}.

    首先,使用基于图卷积神经网络的编码器{f^{(5)}}( \cdot )对节点初始特征矩阵{{\boldsymbol X}}_U^{(5)}{{\boldsymbol X}}_I^{(5)}编码得到节点的嵌入表示{{\boldsymbol p}}_u^{(5)}{{\boldsymbol q}}_i^{(5)},编码过程为:

    [{\boldsymbol p}_{u}^{(5)},{\boldsymbol q}_{i}^{(5)}]={f}^{(5)}({\boldsymbol X}_{U}^{(5)},{\boldsymbol X}_{I}^{(5)},{\boldsymbol M}_{1},{\boldsymbol M}_{2},{\boldsymbol M}_{3},{\boldsymbol M}_{4},{\boldsymbol M}_{5})\text{,} (6)

    其中{{{\boldsymbol M}}_r} \in {\{ 0,1\} ^{m \times n}},r = 1,2,3,4,5为评分r对应的邻接矩阵. 编码器{f^{(5)}}( \cdot )包含一个图卷积层和一个线性层. 在图卷积层中,用户u的向量表示计算过程为:

    \left\{\begin{aligned} & \boldsymbol{h}_u^{(5)}=\sigma\left[accum\left(\displaystyle\sum\limits_{i\in\mathcal{N}_1\left(u\right)}^{ }\boldsymbol{\mu}_{i\to u,1}^{(5)},\dots,\displaystyle\sum\limits_{i\in\mathcal{N}_5\left(u\right)}^{ }\boldsymbol{\mu}_{i\to u,5}^{(5)}\right)\right], \\ & \boldsymbol{\mu}_{i\to u,r}^{(5)}=\frac{1}{\sqrt{\left|\mathcal{N}_r\left(u\right)\right|\left|\mathcal{N}_r\left(i\right)\right|}}\boldsymbol{W}_r^{(5)}\boldsymbol{x}_i^{(5)}, \end{aligned}\right. (7)

    其中\sigma 为ReLu激活函数, accum\left( \cdot \right) 为向量的拼接或者加和. {\mathcal{N}_r}\left( u \right) {\mathcal{N}_r}\left( i \right) 分别表示用户u和项目i在邻接矩阵{{{\boldsymbol M}}_r}中的邻居节点集合. {{\boldsymbol \mu}}_{i \to u,r}^{\left( 5 \right)} 为图卷积过程中项目i传递给用户u的信息. {\boldsymbol{W}}_r^{\left( 5 \right)} 为权重矩阵,{\boldsymbol{x}}_i^{(5)}为项目i的(初始)特征向量. 在图卷积操作后,将用户特征 {\boldsymbol{h}}_u^{(5)} 输入到线性层,线性层输出最终编码后的用户特征:

    {\boldsymbol{p}}_u^{\left( 5 \right)} = \sigma \left( {{\boldsymbol{Wh}}_u^{\left( 5 \right)}} \right) \text{,} (8)

    其中\sigma 为ReLu激活函数,{\boldsymbol{W}}为权重矩阵. 对所有用户节点和项目节点进行编码操作后,可以得到用户和项目的嵌入表示{\boldsymbol{p}}_{\boldsymbol{u}}^{{{(5)}}} \in {\mathbb{R}^d}{\boldsymbol{q}}_{\boldsymbol{i}}^{{{(5)}}} \in {\mathbb{R}^d}d为嵌入表示的维度.

    然后,使用双线性解码器{g^{(5)}}( \cdot )通过预测用户和项目之间的评分类别来完成图的重构. 用户u对项目i评分的计算公式为:

    \begin{aligned} &\hat r_{ui}^{(5)} = {g^{(5)}}\left( {u,i} \right) = {{E}_{p\left( {\hat r_{ui}^{(5)} = r} \right)}}[r] = \displaystyle\sum\limits_{r \in \mathbb{R}} r p\left( {\hat r_{ui}^{(5)} = r} \right), \\ & p\left( {\hat r_{ui}^{(5)} = r} \right) = \frac{{{{\rm e} ^{{{\left( {{{\boldsymbol{p}}_u}} \right)}^{\rm T} }{{\boldsymbol{Z}}_r}{{\boldsymbol{q}}_i}}}}}{{\displaystyle\sum\limits_{s = 1}^R {{{\rm e} ^{{{\left( {{{\boldsymbol{p}}_u}} \right)}^{\rm T}}{{\boldsymbol{Z}}_s}{{\boldsymbol{q}}_i}}}} }}, \\ \end{aligned} (9)

    其中 p\left( {\hat r_{ui}^{(5)} = r} \right) 表示评分 \hat r_{ui}^{(5)} r的概率, {{\boldsymbol{Z}}_r} \in {\mathbb{R}^{d \times d}} 为权重矩阵.

    最后,使用Adam[31]优化器最小化损失函数完成模型的训练:

    {L^{(5)}} = - \displaystyle\sum\limits_{(u,i) \in {D^{(5)}}} {\displaystyle\sum\limits_{r = 1}^5 I } \left[ {r_{ui}^{(5)} = r} \right]\lg p\left( {\hat r_{ui}^{(5)} = r} \right) \text{,} (10)

    其中I\left[ \cdot \right]为指示函数,当 r_{ui}^{(5)} = r 时,其值为1,否则为0. {D^{(5)}}表示有评分 r_{ui}^{(5)} (u,i) 对集合.

    如上所述,我们利用GC-MC算法实现了对目标域活跃用户隐向量和热门项目隐向量的提取.

    类似地,针对 r_{ui}^{(2)} \in \{ 0,1\} 的情况,利用GC-MC算法可以提取辅助域用户隐向量和项目隐向量.

    由于活跃用户和热门项目相关的评分较为丰富,有助于求解相对准确的隐向量特征,本文首先针对活跃用户和热门项目计算隐向量特征,进而建模活跃用户和热门项目在2种评分上对应的隐向量映射关系. 令 {\boldsymbol{p}}_{{u_{\rm a} }}^{(5)} {\boldsymbol{q}}_{{i_{\rm p} }}^{(5)} 分别表示5分制评分矩阵 {{{\boldsymbol R}}^{(5)}} 对应的活跃用户 {u_{\rm a}} (user_active)和热门项目 {i_{\rm p}} (item_popular)隐向量, {\boldsymbol{p}}_{{u_{\rm a} }}^{(2)} {\boldsymbol{q}}_{{i_{\rm p} }}^{(2)} 分别表示二元评分矩阵 {{{\boldsymbol R}}^{(2)}} 对应的活跃用户和热门项目的隐向量.

    基于获取的活跃用户隐向量特征 {\boldsymbol{p}}_{{u_{\rm a} }}^{(2)} {\boldsymbol{p}}_{{u_{\rm a} }}^{(5)} ,我们以 {\boldsymbol{p}}_{{u_{\rm a} }}^{(2)} 作为输入,以 {\boldsymbol{p}}_{{u_{\rm a} }}^{(5)} 作为输出,可以构建深度回归网络学习它们之间的映射关系 {F_1} . 同样,我们可以学习热门项目对应的2种隐向量映射关系 {F_2} . 然而,由于活跃用户和热门项目数量往往偏少,直接构建深度回归网络效果不够理想. 以活跃用户隐向量映射关系建模为例,考虑到推荐平台还存在大量的非活跃用户,他们在辅助域中的评分与目标域上的相比较为丰富,所提取的隐向量更为准确,而且他们的隐向量特征与活跃用户的隐向量特征共享同一特征空间,为进一步提升映射关系建模的准确性,本文映射关系建模时,首先利用大量非活跃用户在辅助域的隐向量特征 {\boldsymbol{p}}_{{u_{\rm ina}}}^{(2)} 作为无监督训练数据训练栈式降噪自编码器(stacked denoising autoencoders,SDAE)[32],获取隐向量特征的低维高层表示. 然后,在编码器的基础上外接一层线性回归单元,构建深度回归网络,并利用少量对应活跃用户的有监督训练数据 \{ {\boldsymbol{p}}_{{u_{\rm a} }}^{(2)},{\boldsymbol{p}}_{{u_{\rm a} }}^{(5)}\} 对深度回归网络进行训练,建模映射关系. 针对栈式降噪自编码器的训练过程如图4所示,其中:图4(a)进行逐层降噪自编码器(denoising autoencoder,DAE)学习;图4(b)将多层降噪自编码器进行拼接;图4(c)利用BP[33]算法对权重微调.

    图  4  利用非活跃用户的辅助域隐向量训练SDAE模型
    Figure  4.  Training the SDAE model with the latent vectors of inactive users in the auxiliary domain

    通常,针对单个降噪自编码器训练时,首先让 {\boldsymbol{x = p}}_{{u_{\rm ina}}}^{(2)} 表示原始的训练数据,将 {\boldsymbol{x}} 添加高斯噪声转化为 {\boldsymbol{\tilde x}} ,其中, {\boldsymbol{\tilde x}}\thicksim N({\boldsymbol{x}},{\sigma ^2}I) . 然后,对 {\boldsymbol{\tilde x}} 进行编码得到低维特征表示:

    {\boldsymbol{y}}{\text{ = }}f{\text{(}}{\boldsymbol{\tilde x}}{\text{) = }}S{\text{(}}{\boldsymbol{W\tilde x+b}}) \text{,} (11)

    其中 {\boldsymbol{W}} {\boldsymbol{b}} 分别表示编码器权值矩阵和偏置向量, S 表示ReLu激活函数. 最后,对 {\boldsymbol{y}} 进行解码得到输入数据的重构数据:

    {\boldsymbol{z}} = g({\boldsymbol{y}}) = S({\boldsymbol{W'y+b'}}) \text{,} (12)

    其中 {\boldsymbol{W}}' {\boldsymbol{b}}' 表示解码器权值和偏置. 损失函数为

    J({\boldsymbol{X}},{\boldsymbol{Z}}) = \frac{1}{2}\displaystyle\sum\limits_{i = 1}^M {||{{\boldsymbol{x}}^{(i)}} - {{\boldsymbol{z}}^{(i)}}|{|^2}} \text{,} (13)

    其中M为样本数.

    在深度回归网络进行训练时,定义损失函数为:

    L = \frac{1}{{2\left| {{U_{\rm a} }} \right|}}\displaystyle\sum\limits_{{u_{\rm a} } \in {U_{\rm a} }} {{{\left\| {{\boldsymbol{\hat p}}_{{u_{\rm a} }}^{(5)}{\boldsymbol{ - p}}_{{u_{\rm a} }}^{(5)}} \right\|}^2}} \text{,} (14)

    其中 {\boldsymbol p}_{{u_{\rm a} }}^{(5)} 是活跃用户 {u_{\rm a}} 基于 {{{\boldsymbol R}}^{(5)}} 矩阵学习得到的隐向量, {\boldsymbol{\hat p}}_{{u_{\rm a} }}^{(5)} = {F_1}({\boldsymbol{p}}_{{u_{\rm a} }}^{(2)}) 是基于深度回归网络预测的隐向量,其中 {\boldsymbol{p}}_{{u_{\rm a} }}^{(2)} 为活跃用户 {u_{\rm a}} 基于 {{{\boldsymbol R}}^{(2)}} 矩阵学习得到的隐向量. 建模过程如图5所示,其中线性回归单元不含有任何激活函数,仅仅计算各个输入单元的加权和. 使用图4中已训练好的SDAE中编码器的最终权重 {\boldsymbol W}'_{1},{\boldsymbol W}'_{2},{\boldsymbol W}'_{3} 初始化深度回归网络中编码器的权重,随机初始化最外层的线性回归单元权重{\boldsymbol W}'_4 . 然后用BP算法对深度回归网络所有权重进行学习,得到最终的深度回归网络,即映射关系 {F_1} .

    图  5  训练深度回归网络
    Figure  5.  Training the deep regression network

    本文的映射关系求解模型符合自教学习[12]范式. 自教学习范式用于在监督分类任务中使用无标记数据提升分类任务的性能,并且该范式不假设未标记的数据与已标记的数据遵循相同的类标签或生成分布. 自教学习范式包含2个阶段:1)使用稀疏编码方法从大量的无标签特征数据中学习得到原始特征的高层表示;2)将有标签训练数据从原始特征空间映射到高层特征表示的新特征空间,得到新的训练样本数据,并进行监督学习. 我们将本文的映射关系建模算法称为基于自教学习深度回归网络的映射关系建模算法. 同样的方法可以用于建模热门项目对应的2种隐向量的映射关系 .

    本文基于自教学习深度回归网络的映射关系建模(self-taught learning based deep regression network for mapping relationship modeling,STLDR)算法如算法1所示. 为描述方便,我们仅以活跃用户映射关系建模为例,该算法返回训练后深度回归网络的所有权重参数统一表示为F1.

    算法1. STLDR算法.

    输入:非活跃用户辅助域隐向量特征 {\boldsymbol p}_{{u_{\rm ina}}}^{(2)} ,活跃用户目标域和辅助域的隐向量特征 {\boldsymbol p}_{{u_{\rm a} }}^{(2)} {\boldsymbol p}_{{u_{\rm a} }}^{(5)}

    输出:活跃用户从辅助域到目标域的映射关系F1.

    [{\boldsymbol W},{\boldsymbol B}] = S DAE{\text{(}}{\boldsymbol p}_{{u_{{\rm ina} }}}^{(2)}{\text{) }}

    /* 基于非活跃用户辅助域隐向量训练SDAE模型*/

    {F_1} = DeepRegression{\text{(}}{\boldsymbol p}_{{u_{\rm a} }}^{(2)},{\boldsymbol p}_{{u_{\rm a} }}^{(5)},{\boldsymbol W},{\boldsymbol B})

    /*利用少量对应活跃用户的有监督训练数据 \{ {\boldsymbol p}_{{u_{\rm a} }}^{(2)},{\boldsymbol p}_{{u_{\rm a} }}^{(5)}\} 对深度回归网络进行训练,并建模映射关系F1*/

    ③ return F1.

    进一步,我们将活跃用户和热门项目对应的隐向量映射关系 {F_1} {F_2} 扩展到目标域全体区域,实现了跨区域映射关系迁移.

    本节研究如何实现辅助域隐向量信息向目标域的迁移. 令 {\boldsymbol p}_{{u_{\rm a} }}^{(5)} 为活跃用户 {u_{\rm a} } 基于评分矩阵 {{{\boldsymbol R}}^{(5)}} 经GC-MC算法学习得到的隐向量, {\boldsymbol q}_{{i_{\rm p}}}^{(5)} 为热门项目 {i_{\rm p} } 基于 {{{\boldsymbol R}}^{(5)}} 经GC-MC算法学习得到的隐向量,跨评分隐向量信息迁移过程为:

    {\boldsymbol{p}}_u^{{\rm transfer} } = \left\{\begin{aligned} &{\boldsymbol{p}}_u^{(5)},\;\;u = {u_{\rm a} }\text{,}\\ &\boldsymbol{p}_u^{(5){F_1}},\;\;u = {u_{\rm ina}}\text{,} \end{aligned} \right. (15)
    {\boldsymbol{q}}_i^{{\rm transfer} } = \left\{ \begin{aligned} &{{\boldsymbol{q}}_i^{(5)},\;\;i = {i_{\rm p}}}\text{,}\\ &{\boldsymbol{q}}_i^{(5){F_2}},\;\;i = i_{\rm unp}\text{,} \end{aligned} \right. (16)

    其中 {\boldsymbol{p}}_{{u_{\rm ina}}}^{(5){F_1}} = {F_1}({\boldsymbol{p}}_{{u_{\rm ina}}}^{(2)}) 为利用映射关系得到的非活跃用户 {u_{\rm ina}} (user_inactive)在目标域上的隐向量, {\boldsymbol{q}}_{{i_{{\rm unp} }}}^{(5){F_2}} = {F_2}({\boldsymbol{q}}_{{i_{\rm unp}}}^{(2)}) 为利用映射关系得到的非热门项目 {i_{\rm unp}} (item_unpopular)在目标域上的隐向量.

    本节研究如何将2.4节中所迁移的知识与目标域原始数值评分进行合理融合. 令 r_{ui}^{(5)} 为数值矩阵 {{{\boldsymbol R}}^{(5)}} 中用户 u 对项目 i 的评分, {\boldsymbol{\bar p}}_u^{(5)} 为本文跨区域跨评分协同过滤模型最终求解的任意用户 u 的隐向量, {\boldsymbol{\bar q}}_i^{(5)} 为最终求解的任意项目 i 的隐向量. {\bar {\boldsymbol z}_r} 为最终学习的双线性解码器对应评分r的权重矩阵, {\bar f^{\left( 5 \right)}}( \cdot ) {\bar g^{\left( 5 \right)}}( \cdot ) 为最终学习的基于图卷积神经网络的编码器和双线性解码器.

    针对目标域具有不同评分密度的各个区域,本文通过对GC-MC算法添加约束实现了可迁移量的迁移. 我们通过求解式(17)中优化问题来获取目标域最终的用户和项目隐向量,实现知识从辅助域和目标域评分密集区域向目标域评分非密集区域的转移.

    \begin{split} \mathrm{min}- &{\displaystyle \displaystyle\sum _{(u,i)}{\displaystyle \displaystyle\sum _{r=1}^{5}I}}\left[{r}_{ui}^{(5)}=r\right]\mathrm{lg}p\left({\hat{r}}_{ui}^{(5)}=r\right) \text+\lambda \Bigg({\left\| {\bar{\boldsymbol q}}_{i}^{(5)}-{\boldsymbol q}_{i}^{\mathrm{\rm transfer}}\right\| }^{2}+\\ &{\left\| {\bar{\boldsymbol p}}_{u}^{(5)}-{\boldsymbol p}_{u}^{\mathrm{\rm transfer}}\right\|}^{2}\Bigg)\text{,}\\[-1pt] \end{split} (17)

    其中 \lambda 为正则化系数,且

    \left\{\begin{aligned} &{\hat{r}}_{ui}^{(5)}={\bar{g}}^{(5)}\left(u,i\right)={E}_{p\left({\hat{r}}_{ui}^{(5)}=r\right)}[r]={\displaystyle \displaystyle\sum _{r\in \mathbb{R}}r}p\left({\hat{r}}_{ui}^{(5)}=r\right)\text{,}\\ & p\left({\hat{r}}_{ui}^{(5)}=r\right)=\frac{{\text{e}}^{{\left({\bar{\boldsymbol p}}_{u}^{(5)}\right)}^{\rm T}{\bar{\boldsymbol Z}}_{r}{\bar{\boldsymbol q}}_{i}^{(5)}}}{{\displaystyle \displaystyle\sum _{s=1}^{R}{\text{e}}^{{\left({\bar{\boldsymbol p}}_{u}^{(5)}\right)}^{\rm T}{\bar{\boldsymbol Z}}_{s}{\bar{\boldsymbol q}}_{i}^{(5)}}}}\text{,}\\ &\left[{\bar{\boldsymbol p}}_{u}^{(5)},{\bar{\boldsymbol q}}_{i}^{(5)}\right]={\bar{f}}^{(5)}\left({\boldsymbol X}_{U}^{(5)},{\boldsymbol X}_{I}^{(5)},{\boldsymbol M}_{1},{\boldsymbol M}_{2},{\boldsymbol M}_{3},{\boldsymbol M}_{4},{\boldsymbol M}_{5}\right). \end{aligned} \right. (18)

    在式(17)中, 采用 {\boldsymbol p}_u^{{\rm transfer} } 对目标域活跃用户和非活跃用户的隐向量进行约束,如果 u 为活跃用户,则 {\boldsymbol p}_u^{{\rm transfer} } = {\boldsymbol p}_u^{(5)} ,即以活跃用户 u 基于评分矩阵 {{{\boldsymbol R}}^{(5)}} 学习得到的隐向量作为约束. 如果 u 为非活跃用户,则 {\boldsymbol p}_u^{{\rm transfer} } = {\boldsymbol p}_u^{(5){F_1}} ,即以非活跃用户 u 基于映射关系得到的隐向量作为约束. 对于项目,采用 {\boldsymbol q}_i^{{\rm transfer} } 对目标域热门项目和非热门项目的隐向量进行约束,如果 i 为热门项目,则 {\boldsymbol q}_i^{{\rm transfer} } = {\boldsymbol q}_i^{(5)} ,即以热门项目 i 基于 {{{\boldsymbol R}}^{(5)}} 学习得到的隐向量作为约束. 如果 i 为非热门项目,则 {\boldsymbol q}_i^{{\rm transfer} } = {\boldsymbol q}_i^{(5){F_2}} ,即以非热门项目 i 基于映射关系得到的隐向量作为约束. 因此,本文通过式(17)的求解实现了知识融合.

    值得注意的是,式(17)中待求解的目标域用户和项目的隐向量维度与 {\boldsymbol p}_u^{{\rm transfer} } {\boldsymbol q}_i^{{\rm transfer} } 相同,也就是与目标域活跃用户和热门项目的隐向量维度相同. 因此,式(17)中目标域用户和项目的隐向量维度不是可调参数,而是固定的. 本文使用Adam优化器求解式(17),上述添加约束的图卷积矩阵补全方法被称为受限图卷积矩阵补全方法,其算法描述将在2.6节给出.

    本节我们给出受限图卷积矩阵补全(restricted graph convolutional matrix completion, Restricted-GC-MC)算法和CRCRCF的完整描述,分别见算法2和算法3.

    算法2. Restricted-GC-MC算法.

    输入:目标域评分矩阵 {{{\boldsymbol R}}^{(5)}} ,目标域用户-商品二部图{G^{(5)}},目标域全体用户和全体项目节点one-hot表示的初始特征矩阵{\boldsymbol X}_U^{(5)}{\boldsymbol X}_I^{(5)},目标域各评分等级对应的邻接矩阵{{\boldsymbol M}_r} \in {\{ 0,1\} ^{m \times n}},r = 1,2,3,4,5,正则化参数 \lambda ,可迁移量 {\boldsymbol p}_u^{{\rm transfer} } (u = {u_1},{u_2}, … ,{u_m}) {\boldsymbol q}_i^{{\rm transfer} } (i = {i_1},{i_2}, … ,{i_n})

    输出:训练后的编码器 {\bar f^{(5)}}( \cdot ) 和解码器 {\bar g^{(5)}}( \cdot ) ,用户隐特征 \bar {\boldsymbol p}_u^{(5)} ,项目隐特征 \bar {\boldsymbol q}_i^{(5)} .

    ① 随机初始化编码器 {\bar f^{(5)}}( \cdot ) 和解码器 {\bar g^{(5)}}( \cdot )

    [{\boldsymbol{\bar p}}_u^{(5)},{\boldsymbol{\bar q}}_i^{(5)}] = {f^{(5)}}({\boldsymbol{X}}_U^{(5)},{\boldsymbol{X}}_I^{(5)},{{\boldsymbol{M}}_1},{{\boldsymbol{M}}_2},{{\boldsymbol{M}}_3},{{\boldsymbol{M}}_4},{{\boldsymbol{M}}_5})

    {J_1} = - \displaystyle\sum\limits_{(u,i)} {\displaystyle\sum\limits_{r = 1}^5 I } \left[ {r_{ui}^{(5)} = r} \right]\lg p\left( {\hat r_{ui}^{(5)} = r} \right) + \lambda \left({\left\| {{\boldsymbol{\bar q}}_i^{(5)}{\boldsymbol{ - q}}_i^{{\rm transfer} }} \right\|^2}+{\left\| {{\boldsymbol{\bar p}}_u^{(5)}{\boldsymbol{ - p}}_u^{{\rm transfer} }} \right\|^2}\right)

    ④ Repeat;

    ⑤  [{\boldsymbol{\bar p}}_u^{(5)},{\boldsymbol{\bar q}}_i^{(5)}] = {\bar f^{(5)}}({\boldsymbol{X}}_U^{(5)},{\boldsymbol{X}}_I^{(5)},{{\boldsymbol{M}}_1},… ,{{\boldsymbol{M}}_5})

    ⑥  for each r_{ui}^{(5)} in {{\boldsymbol R}^{(5)}}

    ⑦    \hat r_{ui}^{\left( 5 \right)} = {\bar g^{\left( 5 \right)}}\left( {\bar {\boldsymbol p}_u^{\left( 5 \right)},\bar {\boldsymbol q}_i^{\left( 5 \right)}} \right)

    ⑧  end for

    ⑨   {J_2} = - \displaystyle\sum\limits_{(u,i)} {\displaystyle\sum\limits_{r = 1}^5 I } \left[ {r_{ui}^{(5)} = r} \right]\lg p\left( {\hat r_{ui}^{(5)} = r} \right)+    \lambda \left({\left\| {{\boldsymbol{\bar q}}_i^{(5)}{\boldsymbol{ - q}}_i^{{\rm transfer} }} \right\|^2}+{\left\| {{\boldsymbol{\bar p}}_u^{(5)}{\boldsymbol{ - p}}_u^{{\rm transfer} }} \right\|^2}\right)

    ⑩   \Delta J = \left| {{J_2} - {J_1}} \right|

    ⑪   {J_1} = {J_2}

    ⑫  更新{\bar f^{\left( 5 \right)}}\left( \cdot \right){\bar g^{\left( 5 \right)}}\left( \cdot \right)的参数;

    ⑬ until ( \Delta J < \delta = {10^{ - 3}} \tau > {T_{\max }} = 100 );

    [{\boldsymbol{\bar p}}_u^{(5)}{\boldsymbol{,\bar q}}_i^{(5)}] = {\bar f^{(5)}}({\boldsymbol{X}}_U^{(5)}{\boldsymbol{,X}}_I^{(5)}{\boldsymbol{,}}{{\boldsymbol{M}}_1},… ,{{\boldsymbol{M}}_5})

    ⑮ return训练后的编码器 {\bar f^{(5)}}( \cdot ) 和解码器 {\bar g^{(5)}}( \cdot ) ,用户隐特征 \bar {\boldsymbol p}_u^{(5)} ,项目隐特征 \bar {\boldsymbol q}_i^{(5)} .

    算法3. CRCRCF算法.

    输入:目标域评分矩阵 {{{\boldsymbol R}}^{(5)}} ,目标域用户-商品二部图{G^{(5)}},目标域全体用户和全体项目节点的初始特征矩阵分别为{\boldsymbol X}_U^{(5)}{\boldsymbol X}_I^{(5)},目标域各评分等级对应的邻接矩阵{\boldsymbol M}_r^{(5)} \in {\{ 0,1\} ^{m \times n}},r = 1,2,3,4,5,辅助域评分矩阵 {{\boldsymbol R}^{(2)}} ,辅助域用户-商品二部图{G^{(2)}},辅助域全体用户和全体项目节点的初始特征矩阵分别为{\boldsymbol{X}}_U^{(2)}{\boldsymbol{X}}_I^{(2)},辅助域各评分等级对应的邻接矩阵{\boldsymbol{M}}_r^{(2)} \in {\{ 0,1\} ^{m \times n}}, r = 0,1,用户活跃度阈值 {\mu _1} ,项目热门度阈值 {\mu _2} ,正则化参数 \lambda

    输出:预测的评分值 {\hat r_{ui}} .

    [{U_{\rm a} },{U_{\rm ina}},{I_{\rm p}},{I_{\rm unp}}] = U ser {\text{-}} Item {\text{-}} Division{\text{(}}{{\boldsymbol{R}}^{(5)}}, {\mu _1},{\mu _2})

    ② [ {\boldsymbol p}_{{u_{\rm a} }}^{(5)} {\boldsymbol q}_{{i_{\rm p} }}^{(5)}]=GC-MC({{\boldsymbol R}^{(5)}}{G^{\left( 5 \right)}} {\boldsymbol M}_r^{\left( 5 \right)} {\boldsymbol X}_U^{\left( 5 \right)}{\boldsymbol X}_I^{\left( 5 \right)});

    ③ [{\boldsymbol p}_{{u_{\rm a} }}^{(2)}{\boldsymbol p}_{{u_{{\rm ina} }}}^{(2)}{\boldsymbol q}_{{i_{\rm p} }}^{(2)}{\boldsymbol q}_{{i_{{\rm unp} }}}^{(2)}]=GC-MC({{\boldsymbol R}^{(2)}}{G^{\left( 2 \right)}} {\boldsymbol M}_r^{\left( 2 \right)} {\boldsymbol X}_U^{\left( 2 \right)}{\boldsymbol X}_I^{\left( 2 \right)});

    T S 1 = ({\boldsymbol p}_{{u_{\rm a} }}^{(2)},{\boldsymbol p}_{{u_{\rm a} }}^{(5)}) T S 2 = ({\boldsymbol q}_{{i_{\rm p} }}^{(2)},{\boldsymbol q}_{{i_{\rm p} }}^{(5)}) ;/*构造监督 学习的训练集*/

    {F_1} = S T LDR({\boldsymbol p}_{{u_{{\rm ina} }}}^{(2)},T S 1){F_2} = S T LDR({\boldsymbol q}_{{i_{{\rm unp} }}}^{(2)},T S 1)

    {\boldsymbol p}_{{u_{{\rm ina} }}}^{(5){F_1}} = {F_1}({\boldsymbol p}_{{u_{{\rm ina} }}}^{(2)}) {\boldsymbol q}_{{i_{{\rm unp} }}}^{(5){F_2}} = {F_2}({\boldsymbol q}_{{i_{{\rm unp} }}}^{(2)})

    {\boldsymbol p}_u^{{\rm transfer} } = \left\{ \begin{aligned} &{{\boldsymbol p}_u^{(5)},\;\;u = {u_{\rm a} }}\\&{\boldsymbol p}_u^{(5){F_1}},\;\;u = u_{{\rm ina} }\end{aligned}\right. {\boldsymbol q}_i^{{\rm transfer} } = \left\{ \begin{aligned} &{{\boldsymbol q}_i^{(5)},\;\;i = {i_{\rm p} }} \\&{\boldsymbol q}_i^{(5){F_2}},\;\;i = i_{{\rm unp} }\end{aligned}\right.

    [{\bar{f}}^{(5)}(\cdot ),{\bar{g}}^{(5)}(\cdot ),{\bar{\boldsymbol p}}_{u}^{(5)},{\bar{\boldsymbol q}}_{i}^{(5)}]=Restricted{\text{-}}GC{\text{-}}MC ({\boldsymbol R}^{(5)}, {G}^{(5)},{\boldsymbol M}_{r}^{(5)},{\boldsymbol X}_{U}^{(5)},{\boldsymbol X}_{I}^{(5)},\lambda ,{\boldsymbol p}_{u}^{\mathrm{\rm transfer}},{\boldsymbol q}_{i}^{\mathrm{\rm transfer}})

    ⑨ return {\hat r_{ui}} = {\bar g^{(5)}}(u,i) .

    1)算法的时间复杂度分析

    假设迭代次数为K,目标域评分数为q,辅助域评分数为\tilde q,用户数和项目数分别为MN,图卷积层输出的隐向量维度k,线性层输出的隐向量维度为d. 本文CRCRCF算法可以分为3个模块:① 使用GC-MC获取目标域和辅助域中用户和项目隐向量; ②基于深度回归网络的映射关系建模; ③目标域评分矩阵的受限图卷积矩阵补全.

    模块①中获取目标域和辅助域矩中用户隐向量和项目隐向量的时间复杂度分别为O(K (5k(M+N)( {\bar N_{\rm T}} ×(M+N)+d)+5qd3))和O(K(2k(M+N)( {\bar N_{S} } (M+N)+d)+2\tilde q{d^3})),且目标域和辅助域的求解用户和项目隐向量过程是完全独立的,可以并行执行,故模块①的时间复杂度为O(K(k(M+N)(max( 5{\bar N_{\rm T}}, 2{\bar N_{\rm S}})(M+N)+d)+max(5q,2\tilde q)d3)),其中,{\bar N_{\text{T}}}{\bar N_{{\rm S}}}为目标域和辅助域用户-商品图中节点的平均邻居数目. 模块②包含层数为F的用户侧和项目侧深度回归网络构建,其时间复杂度为 O((M+ N)\displaystyle\sum\limits_{f = 1}^{F - 1} {{k_f}{k_{f+1}}} ) ,其中 {k_f} 表深度回归网络第f层的维度. 模块③受限于图卷积矩阵补全的时间复杂度与GC-MC算法相同,故本文CRCRCF算法的时间复杂度为O(K(k(M+N)(max(5 {\bar N_{\text{T}}}, 2{\bar N_{{\boldsymbol S}}})(M+N)+d)+max(5q, 2\tilde q)d3+ (M+N)\displaystyle\sum\limits_{f = 1}^{F - 1} {{k_f}{k_{f+1}}} ) +5k(M+N )( {\bar N_{\text{T}}} (M+N)+d)+5qd3).

    2)算法的空间复杂度分析

    算法所需存储空间包括输入数据所需空间和算法参数所需空间. 算法输入数据包括用户和项目的初始特征表示和评分数据,这2部分所需的存储空间分别为 O{(M+N)^2} O3(q+\tilde q) . CRCRCF算法需要存储的参数变量包含3部分: ① 用户和项目的隐向量矩阵和GC-MC模型参数; ②基于自教学习的深度回归网络映射关系建模时的参数和映射后的用户和项目特征矩阵; ③ 限制图卷积矩阵补全模型参数和隐向量矩阵. 这3部分所占用的存储空间为:O(2(M+N)d+ 7(MN+(M+N)k+Kd+{d^2}))O(2\displaystyle\sum\limits_{f = 1}^{F - 1} {({k_f}{k_{f+1}}}+{b_{f{\text{+1}}}})+(M+ N)d)O(5(MN+(M+N)k +Kd+d)+(M+N)d). 因此,CRCRCF算法最终的空间复杂度为O(4(M+N)d+12(MN+(M+N)k+Kd+d2)+2\displaystyle\sum\limits_{f = 1}^{F - 1} {({k_f}{k_{f+1}}}+{b_{f{\text{+1}}}})).

    由以上分析可知,基于GC-MC的隐向量提取导致CRCRCF算法时空复杂度较高. 本文的研究重点在于提高推荐性能,如何在保证性能的同时降低时空复杂度将是后续工作的重点.

    为充分评估CRCRCF的性能,我们将该模型与当前多种经典的推荐算法进行对比. 我们选择MovieLens10M数据集和Netflix数据集进行广泛地实验,实验运行的环境为4.7 GHz,i7-10710U CPU,16 GB RAM, 64位Windows 10. 实验中所涉及算法均使用Python3.6基于2个开源机器学习库Scikit-learn 和PyTorch实现. 本实验主要讨论3个问题:

    1)目标域中活跃用户和热门项目阈值对CRCRCF的性能是否有影响;

    2)相比于其他仅结合辅助域信息的跨评分推荐模型,CRCRCF还充分挖掘目标域活跃用户和热门项目相关的评分密集区域的评分信息,是否可以有效提升目标域整体尤其是评分非密集区域的评分预测性能;

    3)相比于CRCRCF不使用受限图卷积矩阵补全的算法变体CRCRCFdirect以及仅利用少量活跃用户或热门项目在目标域和辅助域中的隐向量进行映射关系学习的算法变体CRCRCFsv,CRCRCF是否更为有效.

    1)GC-MC[11]. 该模型是一种基于图神经网络的评分矩阵补全模型. 实验中设置图卷积层输出的用户和项目的隐向量维度k \in {100,300,500,700,900},线性层输出的用户和项目的隐向量维度d \in {30,45, 60,75,90},dropout比例\rho \in {0.3,0.4,0.5,0.6, 0.7,0.8},参考GC-MC原文,设置图编码器层数l=1. 模型参数的最优值通过交叉验证确定.

    2)CSVD[6]. 该模型是TCF模型[6]的一种变体. 实验中设置隐向量维度 k \in {5,10,15,20,25,30,35, 40},用户隐向量、项目隐向量和评分模式的正则项系数 {\alpha _u} = {\alpha _v} = \beta \in {0.001,0.01,0.1,1,10,100, 1000},辅助域权重 \lambda \in {0.01,0.1,1},并通过交叉验证确定最优参数值.

    3)TMF[8]. 该模型是一种基于混合分解的迁移模型. 实验中设置隐向量维度 k \in {5,10,15,20,25,30,35,40},其余参数参考文献[8]进行设置,即将正则项系数设为0.01,用户画像权重 {w_n} = 1 {w_p} \in {1,2,3,4,5},辅助域权重 \lambda {\text{ = 1}} ,目标域和辅助域的交互系数\rho \in {0.3,0.4,0.5,0.6}.

    4)DLSCF-S[10]. 该模型是一种深度低秩稀疏联合分解模型. 其参数取值参考文献[10]进行设置,即分解层数 l = 2 ,第1层隐向量维度 {k_1}{\text{ = 30}} ,第2层隐向量维度 {k_2} \in \{ {\text{2}},{\text{5}},{\text{7}},{\text{10}},{\text{1}}5,{\text{2}}0\} ,设置辅助域权重 \lambda {\text{ = 1}} ,评分模式系数 {\beta _1} = {\beta _2} \in {0.05,0.1,0.2,0.4,0.6,0.8,1},用户隐向量、项目隐向量的正则项系数 {\alpha _u} = {\alpha _v} = 1 .

    5)EKT[9]. 该模型是一种考虑用户和项目几何结构图信息的矩阵分解模型. 实验中用户、项目的隐向量维度设置为 {k_1} = {k_2} \in {5,10,15,20,25,30,35,40}. 其余参数参考文献[9]进行设置,即辅助域权重 \lambda {\text{ = 1}} ,评分模式矩阵的正则项系数 {\alpha _{\text{s}}} = {\beta _{\text{s}}} = {\gamma _{\text{s}}} = 1,用户目标域和辅助域中隐向量的差值对应的正则项系数以及项目目标域和辅助域中隐向量的差值对应的正则项系数 {\theta _u} = {\theta _v} \in {0.1,0.5,1,5,10},目标域用户、项目的图正则项系数 {\alpha _u} = {\alpha _v} \in {0.01,0.05,0.1,0.5,1},辅助域用户、项目的图正则项系数 {\beta _u} = {\beta _v} \in {0.01,0.05,0.1,0.5,1}.

    6)CRCRCF. 该模型是本文所提模型. 该模型提取隐向量的GC-MC子模块与GC-MC算法设置相同;栈式降噪自编码器模型中的隐含层层数与节点个数依据实验中求得的隐向量维度值进行设置,具体设置方法请见3.4.3节;受限图卷积矩阵补全模型的正则项系数 \lambda \in {0.001,0.01,0.1,1,10,100,1000},其余参数与GC-MC设置相同.

    7)CRCRCFdirect. 该模型是本文所提模型的变体,其不使用受限图卷积矩阵补全,而是将利用映射关系得到的非活跃用户和非热门项目的隐向量直接输入目标域GC-MC训练得到的双线性解码器中预测未知的评分. 提取隐向量的GC-MC子模块与GC-MC算法设置相同;栈式降噪自编码器模型中的隐含层层数与节点个数与CRCRCF算法相同.

    8)CRCRCFsv. 该模型是本文所提模型的变体,该模型仅对少量活跃用户或热门项目在目标域和辅助域中的隐向量进行有监督学习,获取活跃用户以及热门项目在目标域与辅助域上隐向量的映射关系. 提取隐向量的GC-MC子模块与GC-MC算法设置相同. 受限图卷积矩阵补全模型的正则项系数 \lambda \in {0.001,0.01,0.1,1,10,100,1000}.

    本实验采用平均绝对值误差(mean absolute error,MAE)和均方根误差(root mean squared error,RMSE)来衡量评分预测的精度,计算公式为:

    MAE = \frac{1}{{|T|}}\displaystyle\sum\limits_{(u,i) \in T} {\left| {{r_{ui}} - {{\hat r}_{ui}}} \right|} \text{,} (19)
    RMSE=\sqrt{\frac{1}{\left|T\right|}{\displaystyle \displaystyle\sum _{(u,i)\in T}{\left({r}_{ui}-{\hat{r}}_{ui}\right)}^{2}}}\text{,} (20)

    其中 T 表示测试集样本集合, {r_{ui}} {\hat r_{ui}} 分别表示用户 u 对项目 i 的真实评分和预测评分. 通常,测试集上MAERMSE的值越小,推荐算法的评分预测精度越好.

    MovieLens10M(以下简称ML10M)数据集包含7.1 \times 104多个用户对104多个项目的超过107个评分数据,评分的取值范围为{0.5,1,1.5,2,2.5,3,3.5,4,4.5,5}. Netflix数据集包含4.8 \times 105多个用户对1.7 \times 104多个项目的超过108个评分数据,评分的取值范围为{1,2,3,4,5}. 针对本文所讨论的推荐场景,要求实验数据满足:1)目标域和辅助域共享相同的用户集合和项目集合;2)辅助域整体1,0评分比较密集,目标域整体\{1,2,3,4,5\} 评分比较稀疏;3)部分用户对部分项目有2种格式的评分. 因此,参考文献[6]中数据处理方法,本实验中使用的数据集将按照3种方法进行数据处理: 1)将原始数据集中的用户和项目按照评分个数分别排序,然后取评分数量最多的前m个用户和前n个项目的评分数据组成一个密集的评分矩阵 \boldsymbol R ; 2)将 \boldsymbol R 中的评分数据分为3份,即 {{\boldsymbol A}_1} {{\boldsymbol A}_2} {{\boldsymbol A}_3} ,它们含有评分的比例 N({{\boldsymbol A}_1}):N({{\boldsymbol A}_2}):N({{\boldsymbol A}_3}) = 1:1:18 ; 3)将 {{\boldsymbol A}_1} {{\boldsymbol A}_2} 合并作为目标域评分矩阵 {{\boldsymbol R}^{(5)}} (针对ML10M时,目标域评分矩阵记为 {{\boldsymbol R}^{(10)}} ),将 {{\boldsymbol A}_2} {{\boldsymbol A}_3} 合并,并将其中小于4分的评分置为0(不喜欢),大于等于4分的评分置为1(喜欢),以此作为辅助域评分矩阵 {{\boldsymbol R}^{(2)}} .

    需要说明的是,对于目标域评分矩阵 {{\boldsymbol R}^{(10)}} ,GC-MC和Restricted-GC-MC设置 r \in {0.5,1,1.5,2, 2.5,3,3.5,4,4.5,5}即可. 此外,划分 {{\boldsymbol A}_1} {{\boldsymbol A}_2} {{\boldsymbol A}_3} 时,对评分数据不采用随机抽取方式,以避免最终的目标域和辅助域评分矩阵出现空行与空列.

    对照如上数据处理步骤和推荐场景要求,可以发现经过我们的数据处理后,目标域和辅助域的评分密度比为2∶19,目标域评分较为稀疏,辅助域评分较为密集,即满足要求2中跨评分推荐场景实验数据要求;将 {{\boldsymbol A}_2} 分别与 {{\boldsymbol A}_1} {{\boldsymbol A}_3} 合并,构造辅助域和目标域,其目的是满足要求3中推荐场景中目标域和辅助域中部分用户对部分项目有2种格式评分的实验数据要求;此外,目标域和辅助域共享相同的用户集合和项目集合. 因此,经上述操作,实验数据满足要求. 最终实验数据集的统计信息如表1所示.

    表  1  数据集统计信息
    Table  1.  Statistics of the Datasets
    数据集 域名 用户数 项目数 评分格式 评分个数 评分密度/%
    ML10M 目标域 5 000 5 000 [0.5, 5]间隔为0.5 253 673 1.01
    辅助域 5 000 5 000 {0, 1} 2 536 729 10.15
    Netflix 目标域 3 000 3 000 [1, 5]间隔为1 55 024 0.61
    辅助域 3 000 3 000 {0, 1} 574 880 6.39
    下载: 导出CSV 
    | 显示表格

    从上述ML10M和Netflix数据集中目标域评分矩阵的每行中分别选取90%,80%,70%,60%的评分数据作为训练数据集,记为 T {R_{90}} T {R_{80}} T {R_{70}} T {R_{60}} . 将剩下的10%,20%,30%,40%作为测试数据集,记为 T {E_{10}} T {E_{20}} T {E_{30}} T {E_{40}} . 从而可以构造4组不同的训练集和测试集,以更为充分地评估各种不同推荐算法的性能. 值得注意的是,为保证GC-MC算法顺利运行,选取训练集评分的过程中也要避免出现空行和空列.

    通过用户活跃度阈值来划分活跃用户和非活跃用户,阈值越小,则划分的活跃用户数量越少,即映射关系建模时监督训练样本数目越少,不利于映射关系的准确建模. 阈值越大,则活跃用户的评分密度越小,不利于隐向量的准确计算,也将影响映射关系建模的准确性. 因此,用户活跃度阈值过大或者过小均不利于模型学习. 同样,项目热门度阈值过大或者过小也不利于模型学习.

    为了确定最优阈值,我们设定用户的活跃度阈值为 {\mu _1} \in {5%,10%,15%,20%,25%,30%},项目的热门度阈值为 {\mu _2} \in {5%,10%,15%,20%,25%,30%}. 对于ML10M数据集,训练集是 5\;000 \times 5\;000 的评分矩阵,不同阈值对应的活跃用户数和热门项目数分别是250,500,750,10001250,1500. 对于Netflix数据集,训练集是 3\;000 \times 3\;000 的评分矩阵,不同阈值对应的活跃用户数和热门项目数分别是150,300,450,600,750,900.

    如2.3节所述,本文模型通过GC-MC算法分别获取活跃用户和热门项目在目标域和辅助域上的隐向量. GC-MC模型中图卷积层输出的隐向量维度k、线性层输出的隐向量维度d、dropout比例\rho 的最优取值通过交叉验证来确定. 对于ML10M 数据集,经交叉验证确认,目标域不同训练集 T {R_{90}} T {R_{80}} T {R_{70}} T {R_{60}} 和辅助域 {{{\boldsymbol R}}^{(2)}} 上最优的dropout比例依次为0.6,0.6,0.5,0.7,0.5,不同参数 k d 对应的MAE均值情况如图6所示,图6中标注点的前2维数值分别代表参数 k d 的最优取值,第3维数值代表最优参数取值对应的模型在交叉验证过程中的MAE均值. 同样的,在Netflix数据集上也进行同样的操作,此处不再一一列出,仅在表2中给出最优参数组合.

    图  6  GC-MC算法不同 k d 组合对应的MAE均值
    Figure  6.  Average values of MAE corresponding to different combinations of k and d for GC-MC algorithm
    表  2  在Netflix数据集上的GC-MC最优参数取值
    Table  2.  Optimal Parameters Values of GC-MC for Netflix Dataset
    参数 目标域 辅助域
    TR90 TR80 TR70 TR60
    \rho 0.6 0.7 0.5 0.6 0.6
    d 45 45 45 45 80
    k 100 500 500 300 700
    下载: 导出CSV 
    | 显示表格

    对于ML10M 数据集,构建映射关系模型时,在自教学习框架下,首先利用数目众多的非活跃用户和非热门项目的隐向量分别计算用户隐向量和项目隐向量的低维高层特征表示. 根据3.4.2节,辅助域上隐因子向量维度(即线性层的输出维度)为90,故针对用户和项目的映射关系模型的输入向量维度均为90,即 {k_1} =90. 采用栈式降噪自编码器获取输入隐向量的低维高层特征表示,将编码层的层数设置为2. 设定2层编码层中的节点数目为: {k_2} \in {35,40,45,50,55}, {k_3} \in {10,15,20,25,30},通过交叉验证来确定 {k_2} {k_3} 的最优值. 以活跃用户隐向量映射关系建模为例,对应5%,10%,15%,20%,25%,30%等不同活跃度阈值的栈式降噪自编码器算法参数 {k_2} {k_3} 不同组合对应的交叉验证过程的MAE均值如图7所示,其中参数含义与图6类似.

    图  7  用户侧栈式降噪自编码器参数 {k_2} {k_3} 不同组合对应的MAE均值
    Figure  7.  Average values of MAE corresponding to different combinations of {k_2} and {k_3} for SDAE parameters on user-side

    然后在编码器基础上外接一层线性回归单元,利用少量对应活跃用户的有监督训练数据 \{ {\boldsymbol p}_{{u_{\rm a}}}^{(2)},{\boldsymbol p}_{{u_{\rm a}}}^{(5)}\} 建模映射关系.

    同样针对热门项目的隐向量映射关系建模情况的相关实验结果如图8所示,其最优参数情况和迭代收敛情况的分析与图7类似.

    图  8  项目侧栈式降噪自编码器参数 {k_2} {k_3} 不同组合对应的MAE均值
    Figure  8.  Average values of MAE corresponding to different combinations of {k_2} and {k_3} for SDAE parameters on item-side

    对于Netflix数据集,构建映射关系模型的方式与ML10M数据集一样,不同的是对于Netflix数据集,辅助域上用户和项目的隐向量维度为80,故用户侧和项目侧映射关系建模的输入向量维度均为80,即{k_1}=80. 同样设定栈式降噪自编码器的编码层层数为2,根据{k_1}=80,设定2层编码层的节点个数为:{k_2} \in {30,35,40,45,50},{k_3} \in {5,10,15,20,25}. 通过交叉验证来确定 {k_2} {k_3} 的最优值. Netflix数据集上参数调优情况与ML10M 数据集情况相似,为了节约篇幅,此处仅给出最优参数取值,如表3所示.

    表  3  Netflix数据集不同阈值下用户侧和项目侧栈式降噪自编码器最优参数
    Table  3.  The Optimal Parameters of SDAE on User-Side and Item-Side with Different Thresholds for Netflix Dataset
    维度 µ1 µ2
    5% 10% 15% 20% 25% 30% 5% 10% 15% 20% 25% 30%
    k2 30 35 40 45 35 45 30 35 30 45 35 50
    k3 15 20 10 25 20 25 20 20 25 20 25 15
    下载: 导出CSV 
    | 显示表格

    通过映射关系可以基于非活跃用户和非热门项目在辅助域的隐向量预测其在目标域中的隐向量,从而以此为约束求解Restricted-GC-MC模型. 针对每一 {\mu _1} {\mu _2} 组合,利用 T {R_{90}} T {R_{80}} T {R_{70}} T {R_{60}} 训练集训练Restricted-GC-MC,其中图卷积层输出的隐向量维度k和线性层输出的隐向量维度d以及dropout比例\rho 的取值与GC-MC提取目标域隐特征时最优取值一致,参数 \lambda 的最优值通过交叉验证确定. 为节约篇幅,图9仅给出ML10M和Netflix数据集上,当 {\mu _1} = {\mu _{\text{2}}} =0.05时,4种训练集上Restricted-GC-MC不同正则化系数λ∈{0.001,0.01,0.1,1,10,100,1000}对应的MAE均值.

    图  9  {\mu _1} = {\mu _{\text{2}}} = 5%时Restricted-GC-MC不同 \lambda 对应的MAE均值
    Figure  9.  Average values of MAE corresponding to different \lambda for Restricted-GC-MC when {\mu _1} and {\mu _{\text{2}}} equal to 5%

    针对不同用户活跃度阈值和项目热门度阈值组合,采用交叉验证方法确定的最优参数 \lambda 进行Restricted-GC-MC模型训练. 最终,不同阈值组合下CRCRCF算法在ML10M和Netflix数据集上不同测试集上的实验结果如表4表5所示.

    表  4  ML10M数据集上不同活跃度阈值和热门度阈值对应的MAE
    Table  4.  Values of MAE Corresponding to Different Activity Thresholds and Popularity Thresholds for ML10M Dataset
    {\mu _1} {\mu _2} MAE MAE均值 {\mu _1} {\mu _2} MAE MAE均值
    TE10 TE20 TE30 TE40 TE10 TE20 TE30 TE40
    5% 5% 0.6953 0.7011 0.7028 0.7017 0.7002 20% 5% 0.6939 0.7012 0.7045 0.7056 0.7013
    5% 10% 0.6969 0.7188 0.7299 0.7443 0.7225 20% 10% 0.6971 0.7202 0.7298 0.7268 0.7185
    5% 15% 0.6965 0.7001 0.7036 0.7359 0.7090 20% 15% 0.6966 0.7006 0.7038 0.7086 0.7024
    5% 20% 0.6981 0.6998 0.7029 0.7333 0.7085 20% 20% 0.6993 0.6926 0.7013 0.7003 0.6984
    5% 25% 0.7001 0.6995 0.7028 0.7456 0.7120 20% 25% 0.6971 0.6992 0.7001 0.7068 0.7008
    5% 30% 0.6962 0.6992 0.7013 0.7061 0.7007 20% 30% 0.6912 0.6968 0.6983 0.7055 0.6980
    10% 5% 0.6952 0.7006 0.7038 0.7041 0.7009 25% 5% 0.6871 0.7066 0.7026 0.7055 0.7005
    10% 10% 0.6953 0.7189 0.7301 0.7512 0.7239 25% 10% 0.6898 0.7202 0.7311 0.7289 0.7175
    10% 15% 0.6986 0.7022 0.7038 0.7086 0.7033 25% 15% 0.6995 0.7021 0.7039 0.7286 0.7085
    10% 20% 0.7011 0.6995 0.7032 0.6998 0.7009 25% 20% 0.7028 0.7035 0.7151 0.7269 0.7121
    10% 25% 0.6698 0.6735 0.6751 0.6826 0.6753 25% 25% 0.7008 0.7019 0.7177 0.7282 0.7122
    10% 30% 0.6801 0.6887 0.6866 0.6978 0.6883 25% 30% 0.6987 0.7026 0.7089 0.7198 0.7075
    15% 5% 0.6986 0.7033 0.7038 0.7046 0.7026 30% 5% 0.6925 0.6995 0.7249 0.7272 0.7110
    15% 10% 0.6956 0.7189 0.7302 0.7669 0.7279 30% 10% 0.6991 0.7193 0.7297 0.7289 0.7193
    15% 15% 0.6985 0.7012 0.6992 0.7063 0.7013 30% 15% 0.7001 0.6986 0.7031 0.7082 0.7025
    15% 20% 0.6978 0.697 0.6993 0.7051 0.6998 30% 20% 0.7011 0.6956 0.7115 0.7253 0.7084
    15% 25% 0.7003 0.699 0.7022 0.7101 0.7029 30% 25% 0.7026 0.7001 0.7058 0.7088 0.7043
    15% 30% 0.7017 0.7008 0.7029 0.7089 0.7036 30% 30% 0.7088 0.7001 0.7056 0.7086 0.7058
    注:黑体数值表示在ML10M数据集上最优阈值组合结果.
    下载: 导出CSV 
    | 显示表格
    表  5  Netflix数据集上不同活跃度阈值和热门度阈值对应的MAE
    Table  5.  Values of MAE Corresponding to Different Activity Thresholds and Popularity Thresholds for Netflix Dataset
    {\mu _1} \mu_{2} MAE MAE均值 \mu_1 \mu_{2} MAE MAE均值
    TE10 TE20 TE30 TE40 TE10 TE20 TE30 TE40
    5% 5% 0.8343 0.8396 0.8621 0.8811 0.8543 20% 5% 0.8085 0.8101 0.8286 0.8305 0.8194
    5% 10% 0.8328 0.8369 0.8699 0.8655 0.8513 20% 10% 0.8026 0.8035 0.8202 0.8245 0.8127
    5% 15% 0.8288 0.8403 0.8698 0.8683 0.8518 20% 15% 0.8345 0.8315 0.8398 0.8446 0.8376
    5% 20% 0.8281 0.8388 0.8679 0.8856 0.8551 20% 20% 0.8356 0.8337 0.8406 0.8419 0.8380
    5% 25% 0.8372 0.8368 0.8403 0.8919 0.8516 20% 25% 0.8329 0.8353 0.8405 0.8478 0.8391
    5% 30% 0.8351 0.8326 0.8788 0.8968 0.8608 20% 30% 0.8219 0.8347 0.8302 0.8418 0.8322
    10% 5% 0.8301 0.8322 0.8359 0.8826 0.8452 25% 5% 0.8303 0.8329 0.8377 0.8326 0.8334
    10% 10% 0.8281 0.8306 0.8399 0.887 0.8464 25% 10% 0.8326 0.8356 0.8386 0.8578 0.8412
    10% 15% 0.8306 0.8329 0.8782 0.8699 0.8529 25% 15% 0.8313 0.8369 0.8403 0.8609 0.8424
    10% 20% 0.8349 0.8311 0.8409 0.8618 0.8422 25% 20% 0.8301 0.8298 0.8377 0.8499 0.8369
    10% 25% 0.8326 0.8345 0.8591 0.8687 0.8487 25% 25% 0.8336 0.8368 0.8402 0.8587 0.8423
    10% 30% 0.8335 0.8338 0.8369 0.8651 0.8423 25% 30% 0.8324 0.8359 0.8371 0.8524 0.8395
    15% 5% 0.8276 0.8352 0.8349 0.8401 0.8345 30% 5% 0.8349 0.8336 0.8382 0.8809 0.8469
    15% 10% 0.8303 0.8346 0.8386 0.8343 0.8345 30% 10% 0.8321 0.8359 0.8411 0.8863 0.8489
    15% 15% 0.8306 0.8329 0.8399 0.8468 0.8376 30% 15% 0.8312 0.8355 0.8401 0.8869 0.8484
    15% 20% 0.8293 0.8297 0.8421 0.8295 0.8327 30% 20% 0.8311 0.8326 0.8403 0.8717 0.8439
    15% 25% 0.8335 0.8329 0.8386 0.8398 0.8362 30% 25% 0.8346 0.8298 0.8387 0.8933 0.8491
    15% 30% 0.8278 0.8353 0.8388 0.8601 0.8405 30% 30% 0.8367 0.8477 0.8609 0.8971 0.8606
    注:黑体数值表示在Netflix数据集上最优阈值组合结果.
    下载: 导出CSV 
    | 显示表格

    因此,针对本实验要讨论的第1个问题,表4表5的实验结果说明,目标域中活跃用户和热门项目阈值对本文推荐算法的性能的确有影响. 从表4可以看出,在ML10M数据集上,当 {\mu _1} =5%, {\mu _2} =20%时,CRCRCF算法在4种不同测试集上的MAE值具有最小均值0.7027. 从表5中可以看出,在Netflix数据集上,当 {\mu _1} =25%, {\mu _2} =5%时,CRCRCF算法具有最小均值0.8416. {\mu _1} =5%, {\mu _2} =20%和 {\mu _1} =25%, {\mu _2} =5%是2种情况下CRCRCF算法的最优阈值组合.

    当CRCRCF算法取最优活跃用户和热门项目阈值时,我们将测试结果与单域协同过滤算法(如GC-MC)和跨评分协同过滤推荐算法(包括CSVD,TMF,DLSCF-S,EKT)进行对比,表6表7分别列出了ML10M 数据集和Netflix数据集上,CRCRCF和对比方法在不同测试集上的MAE值和RMSE值,以及基于MAE值计算的CRCRCF与对比方法在显著性水平 \alpha =0.05的双尾t检验下的p值. 表8表9则分别列出了ML10M 数据集和Netflix数据集评分非密集区域上不同算法的对比结果.

    表  6  ML10M数据集上不同算法的MAERMSE
    Table  6.  MAE and RMSE Values of Different Algorithms on ML10M Dataset
    算法 MAE RMSE p
    TE10 TE20 TE30 TE40 TE10 TE20 TE30 TE40
    GC-MC 0.7807 0.7819 0.7913 0.7965 0.9971 0.9994 1.0098 1.0146 0.0048
    CSVD 0.7101 0.7180 0.7285 0.7294 0.9110 0.9189 0.9318 0.9359 0.0039
    TMF 0.7207 0.7240 0.7337 0.7387 0.9272 0.9290 0.9414 0.9475 0.0031
    DLSCF-S 0.7069 0.7105 0.7181 0.7186 0.9063 0.9084 0.9178 0.9195 0.0049
    EKT 0.7147 0.7174 0.7238 0.7260 0.9147 0.9182 0.9219 0.9313 0.0040
    CRCRCFsv 0.7266 0.7293 0.7382 0.7402 0.9301 0.9328 0.9459 0.9517 0.0027
    CRCRCFdirect 0.7133 0.7192 0.7301 0.7299 0.9151 0.9223 0.9339 0.9377 0.0037
    CRCRCF(本文) 0.6698 0.6735 0.6751 0.6826 0.8607 0.8756 0.8792 0.8863
    注:黑体数值表示在ML10M数据集上最优的性能指标数据,下划线数字表示次优的性能指标数据.
    下载: 导出CSV 
    | 显示表格
    表  7  Netflix数据集上不同算法的MAERMSE
    Table  7.  MAE and RMSE Values of Different Algorithms on Netflix Dataset
    算法 MAE RMSE p
    TE10 TE20 TE30 TE40 TE10 TE20 TE30 TE40
    GC-MC 0.9037 0.9108 0.9113 0.9347 1.1218 1.1362 1.1383 1.1669 0.0069
    CSVD 0.8462 0.8522 0.8574 0.8656 1.0651 1.0728 1.0756 1.0885 0.0038
    TMF 0.8740 0.8776 0.8825 0.9005 1.0982 1.1106 1.1177 1.1402 0.0016
    DLSCF-S 0.8413 0.8451 0.8491 0.8617 1.0533 1.0626 1.0657 1.0802 0.0045
    EKT 0.8438 0.8511 0.8526 0.8634 1.0587 1.0699 1.0697 1.0857 0.0041
    CRCRCFsv 0.8782 0.8815 0.8876 0.9028 1.1036 1.1219 1.1265 1.1431 0.0014
    CRCRCFdirect 0.8498 0.8571 0.8599 0.8682 1.0694 1.0806 1.0812 1.0921 0.0034
    CRCRCF(本文) 0.8026 0.8035 0.8202 0.8245 1.0062 1.0078 1.0239 1.0276
    注:黑体数值表示在Netflix数据集上最优的性能指标数据,下划线数字表示次优的性能指标数据.
    下载: 导出CSV 
    | 显示表格
    表  8  ML10M数据集评分非密集区域上不同算法的MAERMSE
    Table  8.  MAE and RMSE Values of Different Algorithms on Non-Rating-Dense Region of ML10M Dataset
    算法 MAE RMSE p
    TE10 TE20 TE30 TE40 TE10 TE20 TE30 TE40
    GC-MC 0.8198 0.8209 0.8292 0.8415 1.0391 1.0442 1.0497 1.0659 0.0021
    CSVD 0.7434 0.7453 0.7572 0.7670 0.9528 0.9543 0.9682 0.9845 0.0023
    TMF 0.7500 0.7612 0.7771 0.7781 0.9547 0.9774 0.9981 1.0255 0.0015
    DLSCF-S 0.7355 0.7401 0.7499 0.7545 0.9379 0.9460 0.9585 0.9742 0.0030
    EKT 0.7399 0.7417 0.7551 0.7623 0.9493 0.95 0.9652 0.9803 0.0026
    CRCRCFsv 0.7588 0.7695 0.7809 0.7851 0.9628 0.9856 1.0049 1.0345 0.0012
    CRCRCFdirect 0.7466 0.7437 0.7601 0.7699 0.9572 0.9513 0.9721 0.9887 0.0022
    CRCRCF(本文) 0.6795 0.6846 0.6852 0.6931 0.8789 0.8801 0.9025 0.9133
    注:黑体数值表示在ML10M数据集评分非密集区域上最优的性能指标数据,下划线数字表示次优的性能指标数据.
    下载: 导出CSV 
    | 显示表格
    表  9  Netflix数据集评分非密集区域上不同算法的MAERMSE
    Table  9.  MAE and RMSE Values of Different Algorithms on Non-Rating-Dense Region of Netflix Dataset
    算法 MAE RMSE p
    TE10 TE20 TE30 TE40 TE10 TE20 TE30 TE40
    GC-MC 0.9351 0.9457 0.9768 1.0311 1.1948 1.1976 1.3394 1.3561 0.0033
    CSVD 0.8956 0.8977 0.9090 0.9153 1.1137 1.1181 1.1293 1.1364 0.0027
    TMF 0.8977 0.9100 0.9245 0.9321 1.1290 1.1470 1.1477 1.1508 0.0019
    DLSCF-S 0.8884 0.8946 0.9047 0.9117 1.1102 1.1165 1.1254 1.1321 0.0030
    EKT 0.8894 0.8963 0.9081 0.9131 1.1120 1.1167 1.1284 1.1341 0.0029
    CRCRCFsv 0.9029 0.9201 0.9333 0.9412 1.1368 1.1608 1.1567 1.1601 0.0015
    CRCRCFdirect 0.9022 0.9089 0.9205 0.9238 1.1221 1.1312 1.1421 1.1355 0.0021
    CRCRCF(本文) 0.8221 0.8293 0.8380 0.8429 1.0511 1.0572 1.0629 1.0683
    注:黑体数值表示在Netflix数据集评分非密集区域上最优的性能指标数据,下划线数字表示次优的性能指标数据.
    下载: 导出CSV 
    | 显示表格

    针对本实验要讨论的第2个问题:1)相比于其他仅结合辅助域信息的跨评分推荐模型,CRCRCF是否充分挖掘目标域活跃用户和热门项目相关的评分密集区域的评分信息;2)是否可以有效提升目标域整体尤其是评分非密集区域的评分预测性能. 从表6表7可以看出,CRCRCF在2个数据集的MAERMSE指标上比CSVD,TMF,DLSCF-S,EKT等算法表现更好. 在显著性水平 \alpha =0.05下,根据计算的p值,CRCRCF的性能在2个数据集上均显著优于其他对比方法.

    更进一步,从表8表9可以看出,针对目标域评分非密集区域 {d^{(5)}} ,CRCRCF在MAERMSE指标上比CSVD,TMF,DLSCF-S,EKT等算法具有更为明显的优势. 根据计算的p值,CRCRCF的性能在2个数据集的评分非密集区域上均显著优于其他对比方法.

    此外,从表6~9中可以看出,其他4种跨评分协同过滤推荐算法,如CSVD,TMF,DLSCF-S,EKT,推荐性能均好于单域推荐算法GC-MC. 这主要是因为跨评分协同过滤推荐算法能够迁移辅助域上挖掘到的有价值知识到目标域,有效缓解目标域上数值评分的稀疏性难题.

    上述实验结果说明,CRCRCF能够充分挖掘辅助域较丰富的二元评分和目标域评分密集区域较为丰富的数值评分,针对目标域不同区域制定个性化的知识迁移策略,进而生成更为准确的推荐.

    针对本实验要讨论的第3个问题:相比于CRCRCF不使用受限图卷积矩阵补全的算法变体CRCRCFdirect以及仅利用少量活跃用户或热门项目在目标域和辅助域中的隐向量进行映射关系学习的算法变体CRCRCFsv,CRCRCF是否更为有效. 从表6~9中可以看出,相比于CRCRCFdirect与CRCRCFsv算法, CRCRCF同样在MAERMSE指标上具有明显的优势. 根据计算的p值,CRCRCF的性能在2个数据集整体尤其是评分非密集区域上均显著优于CRCRCFdirect和CRCRCFsv,其主要原因在于,相对于CRCRCFdirect,CRCRCF将利用映射关系得到的非活跃用户和非热门项目的隐向量作为约束条件,可以更为合理地融合目标域数据和辅助域数据,而CRCRCFdirect忽视了目标域数据的价值;相对于CRCRCFsv,CRCRCF基于自教学习范式有效利用了大量非活跃用户或非热门项目在辅助域中的隐向量,可以更精准地建模映射关系,而CRCRCFsv仅利用少量活跃用户或热门项目在目标域和辅助域中的隐向量进行映射关系学习,无法精准建模映射关系.

    本文提出了一种基于迁移学习思想的跨区域跨评分的协同过滤推荐算法(CRCRCF). CRCRCF首先针对活跃用户和热门项目分别建模了辅助域和目标域的隐向量间的映射关系,然后将活跃用户和热门项目的映射关系泛化到全局,依次实现了跨区域映射关系迁移和跨评分的隐向量信息迁移. 最后设计了一种限制图卷积矩阵补全模型实现了目标域信息和辅助域信息的有效融合. CRCRCF可以同时实现辅助域向目标域不同区域的个性化知识迁移,以及目标域密集区域向非密集区域的有效知识迁移. 据我们所知,CRCRCF是首个基于跨区域和跨评分2种思想的推荐算法,通过有效利用辅助域和目标域评分密集区域的信息,CRCRCF可以针对目标域整体,尤其是评分非密集区域进行更为准确的评分预测. 在MovieLens和Netflix数据集上的对比实验说明CRCRCF较其他单域和跨评分推荐算法具有明显的优势. 关于后续工作,CRCRCF仅针对评分信息建模,如何充分利用用户或项目的多模态信息将是我们后续研究的重点.

    作者贡献声明:于旭提出论文的创新思路,负责论文撰写与修改;彭庆龙和詹定佳负责论文撰写;杜军威和刘金环负责实验设计;林俊宇负责算法实现;巩敦卫负责论文修改;张子迎负责数据准备与处理;于婕负责论文修订.

  • 图  1   Wasm生态系统概况

    Figure  1.   Overview of Wasm ecosystem

    图  2   Wasm程序与内存模型

    Figure  2.   Program and memory model of Wasm

    图  3   越界访问漏洞例子

    Figure  3.   An example of out-of-bounds access vulnerabilities

    图  4   类型转换错误例子

    Figure  4.   An example of type coversion error

    图  5   Wasm 线性内存面临的攻击面

    Figure  5.   The attack surface faced by Wasm linear memory

    图  6   间接调用重定向

    Figure  6.   Indirect call redirection

    图  7   Wasmati架构图

    Figure  7.   Architecture diagram of Wasmati

    图  8   WASMAFL 架构图

    Figure  8.   Architecture diagram of WASMAFL

    图  9   Wasabi 架构图

    Figure  9.   Architecture diagram of Wasabi

    图  10   CROW的工作流

    Figure  10.   Workflow of CROW

    图  11   TWINE 架构图

    Figure  11.   Architecture diagram of TWINE

    图  12   Vivienne架构图

    Figure  12.   Architecture diagram of Vivienne

    表  1   Wasm安全研究分类统计

    Table  1   Classification Statistics of Wasm Security Research

    研究方向 篇数 占比/%
    安全实证 4 9.52
    漏洞检测与利用 21 50.00
    安全增强 9 21.43
    形式语义与程序验证 8 19.05
    下载: 导出CSV

    表  2   Wasm安全威胁模型

    Table  2   Security Threat Model of Wasm

    威胁层面 安全漏洞 根因分析
    高级语言支持 越界访问、 由高级语言的不安全特性引入,编译后
    得到的Wasm程序包含易被利用的
    漏洞.
    格式化字符串、
    整型溢出、
    释放后使用
    编译工具链 内存分配器缺陷、 编译工具链无法对高级语言与Wasm的
    差异进行正确转换.
    类型转换错误、
    危险库函数
    二进制表示 非托管栈溢出、 Wasm线性内存的必要安全检查缺失.
    非托管栈上的
    缓冲区溢出、
    堆元数据损坏、
    间接调用重定向
    语言虚拟机 主机环境注入、 Wasm虚拟机或即时编译器的安全
    检查缺失或实现错误.
    侧信道攻击、
    沙箱逃逸
    下载: 导出CSV

    表  3   Wasm 安全实证研究工作总结分析

    Table  3   Summary and Analysis of Empirical Studies on Wasm Security

    研究内容 研究工作 研究数据集 分析方法 开源 主要结论
    高级语言支持 Stiévenart等人[43] 4469个具有缓冲区溢出漏洞的C程序 定量+定性 相同C程序对应的x86程序和Wasm程序的运行结果可能不同,其主要原因在于x86和Wasm在标准库的实现、所提供的安全保护机制和运行环境上存在差异.
    Stiévenart等人[44] 17802个存在漏洞的 C程序 定量+定性
    编译工具链 Romano等人[22] Emscripten的146 个Wasm相关漏洞报告 定量+定性 编译工具链中的漏洞主要来自高级语言与Wasm的同步机制差异、数据类型不兼容、内存模型差异等方面.
    二进制表示 Hilbig等人[85] 来自包管理器和实时网站的8461个Wasm
    二进制文件
    定量+定性 Wasm二进制表示层面的安全威胁主要来自不安全的高级语言特性、非托管栈的错误使用、不安全的外部接口等.
    下载: 导出CSV

    表  4   Wasm 漏洞检测研究工作总结分析

    Table  4   Summary and Analysis of Research Work on Wasm Vulnerability Detection

    检测方法 主要技术 研究工作 具体技术 程序表示 漏洞类型 准确率/% 开源
    静态检测 程序分析 Wassail[88] 信息流分析+污点分析 控制流图 64
    Wasmati[89-90] 数据流分析 代码属性图 内存安全漏洞 92.6
    VeriWasm[91] 抽象解释 控制流图 内存安全漏洞 100
    MinerRay[92] 控制流分析+语义分析 控制流图 加密劫持 99.3
    WANA[93] 符号执行+执行信息分析 二进制程序 智能合约安全 100
    深度学习 MINOS[94] 深度学习 二进制程序 加密劫持 99.0 ×
    动态检测 模糊测试 WAFL[95] 模糊测试+虚拟机快照 二进制程序
    Fuzzm[96] 灰盒模糊测试+金丝雀插桩 二进制程序 内存安全漏洞
    WASAI[97] 混合模糊测试+符号执行 二进制程序 虚假转账 96.6
    WASMAFL[98] 灰盒模糊测试+分层变异算法 虚拟机源程序 ×
    WasmFuzzer[99] 模糊测试+字节码变异算法 虚拟机源程序 ×
    运行时特征分析 MineThrottle[100] 重复执行指令序列分析 二进制程序 加密劫持 69.9 ×
    CoinSpy[101] CPU、内存分析+深度学习 二进制程序 加密劫持 100 ×
    MineSweeper[102] 缓存行为分析+加密原语分析 二进制程序 加密劫持 100
    污点分析 Szanto等人[103] 运行时污点追踪 二进制程序 100 ×
    TaintAssembly[104] 运行时污点追踪 二进制程序 跨语言安全
    混合检测 Wasabi[105] 函数调用插桩+运行时分析 二进制程序
    EVulHunter[106] 控制流分析+运行时检查 控制流图 虚假转账 86.0
    下载: 导出CSV

    表  5   Wasm 安全增强研究工作总结分析

    Table  5   Summary and Analysis of Research Work on Wasm Security Enhancement

    类别 研究工作 关键技术 运行时开销/% 应对的安全威胁 开源 研究进展总结
    静态安全增强 CROW[113] 代码多样化 代码破解 Wasm静态安全增强主要通过对Wasm核心特性和硬件辅助2方面设计安全策略来实现.
    Swivel[114] 控制流一致性+硬件防护 3.3~240.2 幽灵攻击
    MS-Wasm[115] 段式内存 + ARM MTE 35~60 内存安全问题 ×
    Vassena[116] 内存标记 内存安全问题 ×
    动态安全增强 Aerogel[117] 访问控制 18.8~45.9 访问控制缺失 Wasm 动态安全增强主要通过利用运行时和硬件的安全特性来实现.
    SELWasm[118] 自检、加解密、延迟加载 3.45 代码破解 ×
    TWINE[119] Intel SGX 0.9~426.0 执行环境不可信
    WATZ[120] ARM TrustZone 0.02~5 执行环境不可信
    VeriZero[121] 零成本软件故障隔离 22.5~25 上下文转换错误
    下载: 导出CSV

    表  6   Wasm 形式语义与程序验证研究工作总结分析

    Table  6   Summary and Analysis of Research Work on Wasm Formal Semantics and Program Verification

    研究类别 研究工作 发表时间 验证技术 验证工具 被验证的性质 实验数据集 开源
    形式语义 Haas等人[55] 2017-06 执行时间 PolyBenchC
    Watt[141] 2018-01 演绎推理 Isabelle[142] 类型系统可靠性
    Wasm Logic[143] 2018-11 一阶逻辑推理 Isabelle 控制流安全 WebAssembly B树库 ×
    CT-Wasm[144] 2019-01 演绎推理 Isabelle 信息流安全 加密算法库
    Watt等人[145] 2019-10 约束求解 SC-DRF ×
    程序验证 Sjölén[146] 2020-09 关系符号执行 Z3 恒定时间安全 Salsa20
    Vivienne[147] 2021-09 关系符号执行 Z3,CVC4 恒定时间安全 加密算法库
    WASP[148] 2022-06 混合执行 Z3 功能正确性 B树库、加密库 ×
    下载: 导出CSV
  • [1] 杨婷,张嘉元,黄在起,等. 工业控制系统安全综述[J]. 计算机研究与发展,2022,59(5):1035−1053 doi: 10.7544/issn1000-1239.20211154

    Yang Ting, Zhang Jiayuan, Huang Zaiqi, et al. Survey of industrial control systems security[J]. Journal of Computer Research and Development, 2022, 59(5): 1035−1053 (in Chinese) doi: 10.7544/issn1000-1239.20211154

    [2]

    Madakam S, Lake V, Lake V, et al. Internet of things (IoT): A literature review[J]. Journal of Computer and Communications, 2015, 3(3): 164−173

    [3]

    Zheng Zibin, Xie Shaoan, Dai Hongning, et al. Blockchain challenges and opportunities: A survey[J]. Internaltional Journal of Web and Grid Services, 2018, 14(4): 352−375 doi: 10.1504/IJWGS.2018.095647

    [4]

    Monrat A A, Schelén O, Andersson K. A survey of blockchain from the perspectives of applications, challenges, and opportunities[J]. IEEE Access, 2019, 7: 117134−117151 doi: 10.1109/ACCESS.2019.2936094

    [5]

    Varghese B, Wang Nan, Barbhuiya S, et al. Challenges and opportunities in edge computing[C]//Proc of the 2016 IEEE Int Conf on Smart Cloud (SmartCloud). Piscataway, NJ: IEEE, 2016: 20−26

    [6]

    Lynn T, Rosati P, Lejeune A, et al. A preliminary review of enterprise serverless cloud computing (function-as-a-service) platforms[C]//Proc of the 7th IEEE Int Conf on Cloud Computing Technology and Science (CloudCom). Piscataway, NJ: IEEE, 2017: 162−169

    [7]

    Leroy X. Java bytecode verification: Algorithms and formalizations[J]. Journal of Automated Reasoning, 2003, 30(3): 235−269

    [8]

    Microsoft. NET[EB/OL]. [2022-11-07]. https://dotnet.microsoft.com/zh-cn/

    [9]

    W3C Community Group. WebAssembly[EB/OL]. [2022-11-07]. https://webassembly.org/

    [10]

    W3C Community Group. WebAssembly types syntax[EB/OL]. (2023-06-27)[2023-06-27]. https://webassembly.github.io/spec/core/syntax/types.html

    [11]

    W3C Community Group. WebAssembly security document[EB/OL]. [2022-11-07]. https://www.wasm.com.cn/docs/security/

    [12]

    W3C Community Group. WebAssembly execution[EB/OL]. (2023-06-27)[2023-06-27]. https://webassembly.github.io/spec/core/exec/index.html

    [13]

    W3C Community Group. WebAssembly structure[EB/OL]. (2023-06-27)[2023-06-27]. https://webassembly.github.io/spec/core/syntax/index.html

    [14]

    W3C. World Wide Web consortium (W3C) brings a new language tothe Web as WebAssembly becomes a W3C recommendation[EB/OL]. (2019-12-05)[2022-11-07]. https://www.w3.org/2019/12/pressrelease-wasm-rec.html.en

    [15]

    W3C Community Group. WebAssembly roadmap[EB/OL]. [2022-11-07]. https://webassembly.org/roadmap/

    [16]

    ByteCode Alliance. WASI: The WebAssembly system interface[EB/OL]. [2022-11-07]. https://wasi.dev/

    [17]

    CNCF. Wasmcloud: Why stop at the edge[EB/OL]. [2022-11-07]. https://wasmcloud.com/

    [18]

    Secondstate. The second state functions[EB/OL]. [2022-11-07]. https://www.secondstate.io/faas/

    [19]

    Fastly. Faster, simpler, and more secure serverless code[EB/OL]. [2022-11-07]. https://www.fastly.com/products/edge-compute

    [20]

    Gurdeep Singh R, Scholliers C. WARDuino: A dynamic WebAssembly virtual machine for programming microcontrollers[C]//Proc of the 16th ACM SIGPLAN Int Conf on Managed Programming Languages and Runtimes. New York: ACM, 2019: 27−36

    [21]

    CNCF. WasmEdge bring the cloud-native and serverless application paradigms to edge computing[EB/OL]. [2022-11-07]. https://wasmedge.org/

    [22]

    Romano A, Liu Xinyue, Kwon Y, et al. An empirical study of bugs in WebAssembly compilers[C]//Proc of the 36th IEEE/ACM Int Conf on Automated Software Engineering (ASE). Piscataway, NJ: IEEE, 2021: 42−54

    [23]

    McFadden B, Lukasiewicz T, Dileo J, et al. Security chasms of Wasm[EB/OL]. (2018-08-03)[2022-11-07]. https://git.edik.cn/book/awesome-wasm-zh/raw/commit/e046f91804fb5deb95affb52d6348de92c5bd99c/spec/us-18-Lukasiewicz-WebAssembly-A-New-World-of-Native_Exploits-On-The-Web-wp.pdf

    [24]

    Lehmann D, Kinder J, Pradel M. Everything old is new again: Binary security of WebAssembly[C]//Proc of the 29th USENIX Security Symp (USENIX Security 20). Berkeley, CA: USENIX Association, 2020: 217−234

    [25]

    Mozilla. Going public launch bug[EB/OL]. (2015-06-12)[2022-11-7]. https://github.com/WebAssembly/design/issues/150

    [26]

    Yee B, Sehr D, Dardyk G, et al. Native client: A sandbox for portable, untrusted x86 native code[J]. Communications of the ACM, 2010, 53(1): 91−99 doi: 10.1145/1629175.1629203

    [27]

    Mozilla. Asm. js: An extraordinarily optimizable, low-level subset of JavaScript[EB/OL]. [2022-11-07]. http://asmjs.org/

    [28]

    W3C Community Group. WebAssembly core specification W3C recommendation, 2019[EB/OL]. (2019-12-05)[2022-11-07]. https://www.w3.org/TR/wasm-core-1/

    [29]

    Clark L. Standardizing WASI: A system interface to run WebAssembly outside the web[EB/OL]. (2019-03-27)[2022-11-07]. https://hacks.mozilla.org/2019/03/standardizing-wasi-a-webassembly-system-interface/

    [30]

    W3C. WebAssembly core specification 2.0[EB/OL]. (2019-06-27)[2023-06-27]. https://webassembly.github.io/spec/core/_download/WebAssembly.pdf

    [31]

    Attrapadung N, Hanaoka G, Mitsunari S, et al. Efficient two-level homomorphic encryption in prime-order bilinear groups and a fast implementation in webassembly[C]//Proc of the 13th on Asia Conf on Computer and Communications Security. New York: ACM, 2018: 685−697

    [32]

    Deveria A, Schoors L. Can I use WebAssembly[EB/OL]. (2023-06-11)[2023-06-11]. https://caniuse.com/?search=WebAssembly

    [33]

    Hall A, Ramachandran U. An execution model for serverless functions at the edge[C]//Proc of the 5th Int Conf on Internet of Things Design and Implementation. New York: ACM, 2019: 225−236

    [34]

    Hickey P. Edge programming with rust and WebAssembly[EB/OL]. (2018-12-12)[2022-11-07]. https://www.fastly.com/blog/edge-programming-rust-web-assembly

    [35]

    Hickey P. Lucet: Takes WebAssembly beyond the browser fastly[EB/OL]. (2019-03-28)[2022-11-07]. https://www.fastly.com/blog/announcing-lucet-fastly-native-webassembly-compiler-runtime

    [36]

    Varda K. WebAssembly on cloudflare workers[EB/OL]. (2018-10-01)[2022-11-07]. https://blog.cloudflare.com/webassembly-on-cloudflare-workers/

    [37]

    Block. One. EOSIO: Fast, flexible, and forward-driven[EB/OL]. [2022-11-07]. https://eos.io/

    [38]

    McCallum T. Diving into Ethereum’s virtual machine (EVM): The future of Ewasm[EB/OL]. (2019-10-21)[2022-11-07]. https://hackernoon.com/diving-into-ethereums-virtual-machine-the-future-of-ewasm-wrk32iy

    [39]

    Brown A, Sun Mingqiu. A proposed WebAssembly system interface API for machine learning[EB/OL]. [2022-11-07]. https://github.com/WebAssembly/wasi-nn

    [40]

    Stack. Viry3D: A game engine that supports Wasm[EB/OL]. [2022-11-07]. http://www.viry3d.com/

    [41]

    Akinyemi S. Awesome WebAssembly languages[EB/OL]. [2022-11-07]. https://github.com/appcypher/awesome-wasm-langs

    [42]

    Peny P. MicroPython and WebAssembly (Wasm)[EB/OL]. [2022-11-07]. https://github.com/pmp-p/micropython-ports-wasm

    [43]

    Stiévenart Q, De Roover C, Ghafari M. The security risk of lacking compiler protection in WebAssembly[C]//Proc of the 21st IEEE Int Conf on Software Quality, Reliability and Security (QRS). Piscataway, NJ: IEEE, 2021: 132−139

    [44]

    Stiévenart Q, De Roover C, Ghafari M. Security risks of porting C programs to webassembly[C]//Proc of the 37th ACM/SIGAPP Symp on Applied Computing. New York: ACM, 2022: 1713−1722

    [45]

    Astrauskas V, Matheja C, Poli F, et al. How do programmers use unsafe rust?[J]. Proceedings of the ACM on Programming Languages, 2020, 4 (OOPSLA): 1−27

    [46]

    Van Rossum G. Python/C API reference manual[EB/OL]. (2006-09-19)[2022-11-07]. http://sephounet.free.fr/pdf/python/api.pdf

    [47]

    Zakai A, Dawborn T, Shawabkeh M, et al. Emscripten: C/C++ compiler for Wasm[EB/OL]. [2022-11-07]. https://emscripten.org/

    [48]

    Rust Foundation. The Rust programming language[EB/OL]. [2022-11-07]. https://github.com/rust-lang/rust

    [49]

    Rust and WebAssembly Working Group. Wasm-bindgen: Facilitating high-level interactions between Wasm modules and JavaScript[EB/OL]. [2022-11-07]. https://github.com/rustwasm/wasm-bindgen

    [50]

    Near. AssemblyScript: TypeScript complier for Wasm[EB/OL]. [2022-11-07]. https://github.com/AssemblyScript/assemblyscript

    [51]

    van Laethem A, Esteban D, Evans Ron, et al. TinyGo: Go compiler for small places[EB/OL]. [2022-11-07]. https://github.com/tinygo-org/tinygo

    [52]

    W3C Community Group. WebAssembly text format[EB/OL]. (2023-06-27)[2023-06-27]. https://webassembly.github.io/spec/core/text/index.html

    [53]

    W3C. WebAssembly Web API[EB/OL]. (2022-04-19)[2022-11-07]. https://www.w3.org/TR/wasm-web-api-2/

    [54]

    W3C Community Group. Understanding the JS API[EB/OL]. [2022-11-07]. https://webassembly.org/getting-started/js-api/

    [55]

    Haas A, Rossberg A, Schuff D L, et al. Bringing the Web up to speed with WebAssembly[C]//Proc of the 38th ACM SIGPLAN Conf on Programming Language Design and Implementation. New York: ACM, 2017: 185−200

    [56]

    Google. What is V8[EB/OL]. [2022-11-07]. https://v8.dev/

    [57]

    Mozilla. SpiderMonkey: Mozilla’s JavaScript and WebAssembly engine[EB/OL]. [2022-11-07]. https://spidermonkey.dev/

    [58]

    Akinyemi S. Awesome WebAssembly runtimes[EB/OL]. [2022-11-07]. https://github.com/appcypher/awesome-wasm-runtimes

    [59]

    Block. One. EOS VM: EOSIO[EB/OL]. [2022-11-07]. https://eos.io/for-developers/build/eos-vm/

    [60]

    Intel. WebAssembly micro runtime[EB/OL]. [2022-11-07]. https://github.com/bytecodealliance/wasm-micro-runtime

    [61]

    Bytecode Alliance. Wasmtime: A standalone runtime for WebAssembly[EB/OL]. [2022-11-07]. https://github.com/bytecodealliance/wasmtime

    [62]

    Akbary S, Chaudry W, Chevalier S, et al. Run any code on any client with WebAssembly and Wasmer[EB/OL]. [2022-11-07]. https://wasmer.io/

    [63]

    D’Antras A. Double free vulnerability in wasmtime[EB/OL]. (2021-12-04)[2022-11-07]. https://github.com/bytecodealliance/wasmtime/pull/3582

    [64]

    Crichton A. x64: Incorrect codegen for f32x4. abs v128. not[EB/OL]. (2021-09-11)[2022-11-07]. https://github.com/bytecodealliance/wasmtime/issues/3327

    [65]

    McCaskey M. Sandbox excape in wasmer[EB/OL]. (2020-10-24)[2022-11-07]. https://github.com/wasmerio/wasmer/issues/1759

    [66]

    Morrisett G, Walker D, Crary K, et al. From system F to typed assembly language[J]. ACM Transactions on Programming Languages and Systems, 1999, 21(3): 527−568 doi: 10.1145/319301.319345

    [67]

    Necula G C. Proof-carrying code[C]//Proc of the 24th ACM SIGPLAN-SIGACT Symp on Principles of Programming Languages. New York: ACM, 1997: 106−119

    [68]

    Wahbe R, Lucco S, Anderson T E, et al. Efficient software-based fault isolation[C]//Proc of the 14th ACM Symp on Operating Systems Principles. New York: ACM, 1993: 203−216

    [69]

    Pierce B C. Types and Programming Languages[M]. Cambridge, MA: MIT press, 2002: 1−13

    [70]

    Damas L, Milner R. Principal type-schemes for functional programs[C]//Proc of the 9th ACM SIGPLAN-SIGACT Symp on Principles of Programming Languages. New York: ACM, 1982: 207−212

    [71]

    Kozen D, Tseng W L D. The Böhm–Jacopini theorem is false, propositionally[C]//Proc of the 9th Int Conf on Mathematics of Program Construction. Berlin: Springer, 2008: 177−192

    [72]

    Lindholm T, Yellin F, Bracha G, et al. The Java virtual machine specification[EB/OL]. (2013-02-28)[2023-06-27]. https://docs.oracle.com/javase/specs/jvms/se7/html/

    [73]

    Arce I. The Shellcode generation[J]. IEEE Security & Privacy, 2004, 2(5): 72−76

    [74]

    Abadi M, Budiu M, Erlingsson U, et al. Control-flow integrity principles, implementations, and applications[J]. ACM Transactions on Information and System Security, 2009, 13(1): 1−40

    [75]

    Zhang Chao, Wang Tielei, Wei Tao, et al. IntPatch: Automatically fix integer-overflow-to-buffer-overflow vulnerability at compile-time[C]//Proc of the 15th European Symp on Research in Computer Security. Berlin: Springer, 2010: 71−86

    [76]

    John B. Memory safety: Old vulnerabilities become new with WebAssembly[EB/OL]. (2018-12-06)[2022-11-07]. https://www.forcepoint.com/blog/x-labs/new-whitepaper-memory-safety-old-vulnerabilities-become-new-webassembly

    [77]

    Lea D. A memory allocator[EB/OL]. (2000-04-04)[2022-11-07]. https://gee.cs.oswego.edu/dl/html/malloc.html

    [78] 陈小全,薛锐. 程序漏洞:原因、利用与缓解——以C和C++语言为例[J]. 信息安全学报,2017,2(4):41−56

    Chen Xiaoquan, Xue Rui. Cause, exploitation and mitigation of program vulnerability—C and C++ language as an example[J]. Journal of Cyber Security, 2017, 2(4): 41−56 (in Chinese)

    [79]

    Zakai A, Dawborn T, Shawabkeh M, et al. Emscripten file system API[EB/OL]. [2022-11-07]. https://emscripten.org/docs/api_reference/Filesystem-API.html

    [80] Cowan C, Wagle F, Pu C, et al. Buffer overflows: Attacks and defenses for the vulnerability of the decade[C]//Proc of the 2000 DARPA Information Survivability Conf and Exposition. Piscataway, NJ: IEEE, 2000: 119−129

    Cowan C,Wagle F,Pu C,et al. Buffer overflows:Attacks and defenses for the vulnerability of the decade[C]//Proc of the 2000 DARPA Information Survivability Conf and Exposition. Piscataway,NJ:IEEE,2000:119−129

    [81]

    Gisbert H M, Ripoll I. On the effectiveness of nx, ssp, renewssp, and aslr against stack buffer overflows[C]//Proc of the 13th IEEE Int Symp on Network Computing and Applications. Piscataway, NJ: IEEE, 2014: 145−152

    [82]

    Dhem J F, Koeune F, Leroux P A, et al. A practical implementation of the timing attack[C]//Proc of the 3rd Int Conf on Smart Card Research and Advanced Applications. Berlin: Springer, 1998: 167−182

    [83]

    Kocher P, Horn J, Fogh A, et al. Spectre attacks: Exploiting speculative execution[J]. Communications of the ACM, 2020, 63(7): 93−101 doi: 10.1145/3399742

    [84]

    Richards G, Hammer C, Burg B, et al. The eval that men do[C]//Proc of the 25th European Conf on Object-Oriented Programming. Berlin: Springer, 2011: 52−78

    [85]

    Hilbig A, Lehmann D, Pradel M. An empirical study of real-world webassembly binaries: Security, languages, use cases[C]//Proc of the 30th Web Conf 2021. New York: ACM, 2021: 2696−2708

    [86]

    NSA Center. Juliet C/C++ 1.3[EB/OL]. (2017-10-01)[2022-11-07]. https://samate.nist.gov/SARD/test-suites/112

    [87] Lattner C, Adve V. LLVM: A compilation framework for lifelong program analysis & transformation[C]//Proc of the 2004 Int Symp on Code Generation and Optimization. Piscataway, NJ: IEEE, 2004: 75−86

    Lattner C,Adve V. LLVM:A compilation framework for lifelong program analysis & transformation[C]//Proc of the 2004 Int Symp on Code Generation and Optimization. Piscataway,NJ:IEEE,2004:75−86

    [88]

    Stiévenart Q, De Roover C. Compositional information flow analysis for WebAssembly programs[C]//Proc of the 20th IEEE Int Working Conf on Source Code Analysis and Manipulation (SCAM). Piscataway, NJ: IEEE, 2020: 13−24

    [89]

    Lopes P. Discovering vulnerabilities in WebAssembly with code property graphs[EB/OL]. [2022-11-07]. https://www.inesc-id.pt/publications/17400/pdf/

    [90] Brito T, Lopes P, Santos N, et al. Wasmati: An efficient static vulnerability scanner for WebAssembly[J]. Computers & Security, 2022, 118: 102745

    Brito T,Lopes P,Santos N,et al. Wasmati:An efficient static vulnerability scanner for WebAssembly[J]. Computers & Security,2022,118:102745

    [91]

    Johnson E, Thien D, Alhessi Y, et al. Доверяй, но проверяй: SFI safety for native-compiled Wasm[C]//Proc of the 28th Network and Distributed System Security Symp (NDSS). Reston, VA: The Internet Society, 2021

    [92]

    Romano A, Zheng Y, Wang W. MinerRay: Semantics-aware analysis for ever-evolving cryptojacking detection[C]//Proc of the 35th IEEE/ACM Int Conf on Automated Software Engineering (ASE). Piscataway, NJ: IEEE, 2020: 1129−1140

    [93]

    Wang Dong, Jiang Bo, Chan W K. WANA: Symbolic execution of Wasm bytecode for cross-platform smart contract vulnerability detection[J]. arXiv preprint, arXiv: 2007.15510, 2020

    [94]

    Naseem F N, Aris A, Babun L, et al. MINOS: A lightweight real-time cryptojacking detection system[C]//Proc of the 28th Network and Distributed System Security Symp (NDSS). Reston, VA: The Internet Society, 2021

    [95]

    Haßler K, Maier D. WAFL: Binary-only WebAssembly fuzzing with fast snapshots[C]//Proc of the 5th Reversing and Offensive-oriented Trends Symp. New York: ACM 2021: 23−30

    [96]

    Lehmann D, Torp M T, Pradel M. Fuzzm: Finding memory bugs through binary-only instrumentation and fuzzing of WebAssembly[J]. arXiv preprint, arXiv: 2110.15433, 2021

    [97]

    Chen Weimin, Sun Zihan, Wang Haoyu, et al. WASAI: Uncovering vulnerabilities in Wasm smart contracts[C]//Proc of the 31st ACM SIGSOFT Int Symp on Software Testing and Analysis. New York: ACM, 2022: 703−715

    [98] 林敏,张超. 针对 WebAssembly 虚拟机的模糊测试方案[J]. 网络安全技术与应用,2020,2(6):15−18 doi: 10.3969/j.issn.1009-6833.2020.06.011

    Lin Min, Zhang Chao. Fuzzing scheme for WebAssembly virtual machine[J]. Network Security Technology & Application, 2020, 2(6): 15−18 (in Chinese) doi: 10.3969/j.issn.1009-6833.2020.06.011

    [99]

    Jiang Bo, Li Zichao, Huang Yuhe, et al. WasmFuzzer: A fuzzer for WebAssembly virtual machines[C]//Proc of the 34th Int Conf on Software Engineering and Knowledge Engineering (SEKE 2022). Pittsburgh, Pennsylvania: KSIR Virtual Conf Center, 2022: 537−542

    [100]

    Bian Weikang, Meng Wei, Zhang Mingxue. MineThrottle: Defending against Wasm in-browser cryptojacking[C]//Proc of the 29th ACM Web Conf 2020. New York: ACM, 2020: 3112−3118

    [101]

    Kelton C, Balasubramanian A, Raghavendra R, et al. Browser-based deep behavioral detection of web cryptomining with CoinSpy[C]//Proc of the 2020 Workshop on Measurements, Attacks, and Defenses for the Web (MADWeb). Reston, VA: The Internet Society, 2020. 2020: 1−12

    [102]

    Konoth R K, Vineti E, Moonsamy V, et al. MineSweeper: An in-depth look into drive-by cryptocurrency mining and its defense[C]//Proc of the 25th ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2018: 1714−1730

    [103]

    Szanto A, Tamm T, Pagnoni A. Taint tracking for WebAssembly[J]. arXiv preprint, arXiv: 1807.08349, 2018

    [104]

    Fu W, Lin R, Inge D. TaintAssembly: Taint-based information flow control tracking for WebAssembly[J]. arXiv preprint, arXiv: 1802.01050, 2018

    [105]

    Lehmann D, Pradel M. Wasabi: A framework for dynamically analyzing WebAssembly[C]//Proc of the 24th Int Conf on Architectural Support for Programming Languages and Operating Systems. New York: ACM, 2019: 1045−1058

    [106]

    Quan Lijin, Wu Lei, Wang Haoyu. EVulHunter: Detecting fake transfer vulnerabilities for EOSIO’s smart contracts at WebAssembly-level[J]. arXiv preprint, arXiv: 1906.10362, 2019

    [107]

    Yamaguchi F, Golde N, Arp D, et al. Modeling and discovering vulnerabilities with code property graphs[C]//Proc of the 35th IEEE Symp on Security and Privacy. Piscataway, NJ: IEEE, 2014: 590−604

    [108]

    Bytecode Alliance. Lucet: A native WebAssembly compiler and runtime[EB/OL]. [2022-11-07]. https://github.com/bytecodealliance/lucet

    [109]

    Dan. Javascript obfuscate and encoder[EB/OL]. [2022-11-07]. https://www.cleancss.com/javascript-obfuscate/index.php.

    [110]

    Gu Jiuxiang, Wang Zhenhua, Kuen J, et al. Recent advances in convolutional neural networks[J]. Pattern Recognition, 2018, 77: 354−377 doi: 10.1016/j.patcog.2017.10.013

    [111]

    Fioraldi A, Maier D, Eißfeldt H, et al. AFL++: Combining incremental steps of fuzzing research[C]//Proc of the 14th USENIX Workshop on Offensive Technologies (WOOT 20). Berkeley, CA: USENIX Association 2020

    [112]

    Musch M, Wressnegger C, Johns M, et al. New kid on the Web: A study on the prevalence of WebAssembly in the wild[C]//Proc of the 16th Int Conf on Detection of Intrusions and Malware, and Vulnerability Assessment. Berlin: Springer, 2019: 23−42

    [113]

    Cabrera Arteaga J, Floros O, Vera Perez O, et al. CROW: Code diversification for Webassembly[C]//Proc of the 2021 Workshop on Measurements, Attacks, and Defenses for the Web (MADWeb), Reston, VA, USA: The Internet Society, 2021

    [114]

    Narayan S, Disselkoen C, Moghimi D, et al. Swivel: Hardening WebAssembly against Spectre[C]//Proc of the 30th USENIX Security Symp (USENIX Security 21). Berkeley, CA: USENIX Association, 2021: 1433−1450

    [115]

    Disselkoen C, Renner J, Watt C, et al. Position paper: Progressive memory safety for WebAssembly[C]//Proc of the 8th Int Workshop on Hardware and Architectural Support for Security and Privacy. New York: ACM, 2019: 1−8

    [116]

    Vassena M, Patrignani M. Memory safety preservation for WebAssembly[C/OL]//Proc of the 47th ACM SIGPLAN Symp on Principles of Programming Languages. New York: ACM, 2020[2022-11-07]. https://people.cispa.io/marco.vassena/publications_files/sc-wasm.pdf

    [117]

    Liu Renju, Garcia L, Srivastava M. Aerogel: Lightweight access control framework for WebAssembly-based bare-metal IoT devices[C]//Proc of the 6th IEEE/ACM Symp on Edge Computing (SEC). Piscataway, NJ: IEEE, 2021: 94−105

    [118]

    Sun Jian, Cao Dingyuan, Liu Ximing, et al. SELWasm: A code protection mechanism for WebAssembly[C]//Proc of the 2019 IEEE Int Conf on Parallel & Distributed Processing with Applications, Big Data & Cloud Computing, Sustainable Computing & Communications, Social Computing & Networking (ISPA/BDCloud/SocialCom/SustainCom). Piscataway, NJ: IEEE, 2019: 1099−1106

    [119]

    Ménétrey J, Pasin M, Felber P, et al. TWINE: An embedded trusted runtime for WebAssembly[C]//Proc of the 37th IEEE Int Conf on Data Engineering (ICDE). Piscataway, NJ: IEEE, 2021: 205−216

    [120]

    Ménétrey J, Pasin M, Felber P, et al. WATZ: A trusted WebAssembly runtime environment with remote attestation for TrustZone[J]. arXiv preprint, arXiv: 2206.08722, 2022

    [121]

    Kolosick M, Narayan S, Johnson E, et al. Isolation without taxation: Near-zero-cost transitions for WebAssembly and SFI[J]. Proceedings of the ACM on Programming Languages, 2022, 6(POPL): 1−30

    [122]

    Jacob M, Jakubowski M H, Naldurg P, et al. The superdiversifier: Peephole individualization for software protection[C]//Proc of the 3rd Int Workshop on Security. Berlin: Springer, 2008: 100−120

    [123]

    Sasnauskas R, Chen Y, Collingbourne P, et al. Souper: A synthesizing superoptimizer[J]. arXiv preprint, arXiv: 1711.04422, 2017

    [124]

    Moura L, Bjørner N. Z3: An efficient SMT solver[C]//Proc of the 14th Int Conf on Tools and Algorithms for the Construction and Analysis of Systems. Berlin: Springer, 2008: 337−340

    [125]

    Denis F, Bernstein D J, Percival C, et al. The sodium cryptography library[EB/OL]. [2022-11-07]. https://download.libsodium.org/doc/

    [126]

    Google. TurboFan: A V8’s optimizing compilers[EB/OL]. [2022-11-07]. https://v8.dev/docs/turbofan

    [127]

    Akritidis P, Costa M, Castro M, et al. Baggy bounds checking: An efficient and backwards-compatible defense against out-of-bounds errors[C]//Proc of the 18th USENIX Security Symp. Berkeley, CA: USENIX Association, 2009

    [128]

    Nagarakatte S, Zhao Jianzhou, Martin M M K, et al. SoftBound: Highly compatible and complete spatial memory safety for C[C]//Proc of the 30th ACM SIGPLAN Conf on Programming Language Design and Implementation. New York: ACM, 2009: 245−258

    [129]

    Van Der Kouwe E, Nigade V, Giuffrida C. Dangsan: Scalable use-after-free detection[C]//Proc of the 12th European Conf on Computer Systems. New York: ACM, 2017: 405−419

    [130]

    OW2 consortium. ASM: An all purpose Java bytecode manipulation and analysis framework[EB/OL]. (2022-10-02)[2022-11-07]. https://asm.ow2.io/

    [131]

    Vallée-Rai R, Co P, Gagnon E, et al. Soot: A Java bytecode optimization framework[C]//Proc of the 1999 Conf of the Centre for Advanced Studies on Collaborative Research. Indianapolis, Indiana: IBM, 1999

    [132]

    Intel. What is Intel SGX[EB/OL]. [2023-06-27]. https://www.intel.com/content/www/us/en/architecture-and-technology/software-guard-extensions.html

    [133]

    Sabt M, Achemlal M, Bouabdallah A. Trusted execution environment: What it is, and what it is not[C]//Proc of the 14th IEEE Trustcom/BigDataSE/ISPA. Piscataway, NJ: IEEE, 2015: 57−64

    [134]

    Bellard F. QEMU, a fast and portable dynamic translator[C]//Proc of the FREENIX Track: 2005 USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2005: 41−46

    [135]

    SQLite Consortium. SQLite home page[EB/OL]. (2022-09-29)[2022-11-07]. https://www.sqlite.org/index.html

    [136]

    Priebe C, Muthukumaran D, Lind J, et al. SGX-LKL: Securing the host OS interface for trusted execution[J]. arXiv preprint, arXiv: 1908.11143, 2019

    [137]

    Pinto S, Santos N. Demystifying ARM TrustZone: A comprehensive survey[J]. ACM Computing Surveys, 2019, 51(6): 1−36

    [138]

    Coker G, Guttman J, Loscocco P, et al. Principles of remote attestation[J]. International Journal of Information Security, 2011, 10(2): 63−81 doi: 10.1007/s10207-011-0124-7

    [139]

    Kaplan D, Powell J, Woller T. AMD memory encryption[EB/OL]. (2021-10-18)[2022-11-07]. https://www.amd.com/system/files/TechDocs/memory-encryption-white-paper.pdf

    [140]

    Lee D, Kohlbrenner D, Shinde S, et al. Keystone: An open framework for architecting trusted execution environments[C]//Proc of the 15th European Conf on Computer Systems. New York: ACM, 2020: 1−16

    [141]

    Watt C. Mechanising and verifying the WebAssembly specification[C]//Proc of the 7th ACM SIGPLAN Int Conf on Certified Programs and Proofs. New York: ACM, 2018: 53−65

    [142]

    Nipkow T, Wenzel M, Paulson LC. Isabelle/HOL: A Proof Assistant for Higher-Order Logic[M]. Berlin: Springer, 2002

    [143]

    Watt C, Maksimović P, Krishnaswami N R, et al. A program logic for first-order encapsulated WebAssembly[C]//Proc of the 33rd European Conf on Object-Oriented Programming. Berlin: Springer, 2019

    [144]

    Watt C, Renner J, Popescu N, et al. CT-Wasm: Type-driven secure cryptography for the web ecosystem[J]. Proceedings of the ACM on Programming Languages, 2019, 3(POPL): 1−29

    [145]

    Watt C, Rossberg A, Pichon-Pharabod J. Weakening WebAssembly[J]. Proceedings of the ACM on Programming Languages, 2019, 3(OOPSLA): 1−28

    [146]

    Sjölén J. Relational symbolic execution in WebAssembly[D]. Stockholm, Sweden: KTH, School of Electrical Engineering and Computer Science (EECS), 2020

    [147]

    Tsoupidi R M, Balliu M, Baudry B. Vivienne: Relational verification of cryptographic implementations in WebAssembly[C]//Proc of the 6th IEEE Secure Development Conf (SecDev). Piscataway, NJ: IEEE, 2021: 94−102

    [148]

    Marques F, Fragoso Santos J, Santos N, et al. Concolic execution for WebAssembly[C]//Proc of the 36th European Conf on Object-Oriented Programming (ECOOP 2022). Berlin: Springer, 2022

    [149]

    Cann R. Formal Semantics: An Introduction[M]. Cambridge, UK: Cambridge University Press, 1993

    [150]

    Adve S V, Gharachorloo K. Shared memory consistency models: A tutorial[J]. Computer, 1996, 29(12): 66−76 doi: 10.1109/2.546611

    [151]

    Hoare C A R. Communicating sequential processes[J]. Communications of the ACM, 1978, 21(8): 666−677 doi: 10.1145/359576.359585

    [152]

    Fetzer J H. Program verification: The very idea[J]. Communications of the ACM, 1988, 31(9): 1048−1063 doi: 10.1145/48529.48530

    [153]

    Sozeau M, Bertot Y, Dénès M, et al. The Coq proof assistant[EB/OL]. [2023-06-27]. https://coq.inria.fr/

    [154]

    Farina G P, Chong S, Gaboardi M. Relational symbolic execution[C]//Proc of the 21st Int Symp on Principles and Practice of Declarative Programming. New York: ACM, 2019: 1−14

    [155]

    Bernstein D J. The Salsa20 Family of Stream Ciphers[M]//New Stream Cipher Designs. Berlin: Springer, 2008: 84−97

    [156] 张芸,刘佳琨,夏鑫,等. 基于信息检索的软件缺陷定位技术研究进展[J]. 软件学报,2020,31(8):2432−2452

    Zhang Yun, Liu Jiakun, Xia Xin, et al. Research progress on software bug localization technology based on information retrieval[J]. Journal of Software, 2020, 31(8): 2432−2452 (in Chinese)

    [157]

    Ghanbari A, Benton S, Zhang Lingming. Practical program repair via bytecode mutation[C]//Proc of the 28th ACM SIGSOFT Int Symp on Software Testing and Analysis. New York: ACM, 2019: 19−30

    [158]

    Jia Yue, Harman M. An analysis and survey of the development of mutation testing[J]. IEEE Transactions on Software Engineering, 2010, 37(5): 649−678

    [159]

    Microsoft. Dafny[EB/OL]. [2022-11-07]. https://dafny.org/

    [160]

    Toccata. Why3: Where programs meet provers[EB/OL]. [2022-11-07]. http://why3.lri.fr/

    [161]

    Jacobs B, Smans J, Piessens F, et al. VeriFast: A research prototype of a tool for modular formal verification[EB/OL]. (2021-04-21)[2022-11-07]. https://github.com/verifast/verifast

  • 期刊类型引用(0)

    其他类型引用(2)

图(12)  /  表(6)
计量
  • 文章访问数:  349
  • HTML全文浏览量:  102
  • PDF下载量:  133
  • 被引次数: 2
出版历程
  • 收稿日期:  2023-01-29
  • 修回日期:  2023-08-15
  • 网络出版日期:  2024-03-13
  • 刊出日期:  2024-11-30

目录

/

返回文章
返回