Provably Secure Decisions Based on Potentially Malicious Trust Ratings
Lead Research Organisation:
University of Oxford
Department Name: Computer Science
Abstract
Anyone who uses the internet will be aware of ratings and reviews, for example when booking a hotel. How much trust can we place in reviews we read online? Perhaps internet trolls bombarded a site with negative ratings, or perhaps a company's PR person wrote something glowingly positive for their client? Most people have a degree of skepticism. Ratings can also be used behind the screens, for example when flagging possible malware. Can we automate decisions based on ratings? Is there a formulaic way of using the ratings without being deceived? Our research proposes a foundation to enable secure decisions based on ratings.
Ratings are especially important in open networks, which play a large role in the internet of things. In open networks, participants are potentially malicious (attackers), yet we may rely on information that they provide. In current analysis of networks that use potentially unfair ratings, assumptions are made about the attackers. For example, that they maximise their profit, or want to perform specific actions. In reality, however, we cannot know what the attackers want or will do. This is the crucial challenge in our approach: we provide solutions with a proven risk-bound, regardless of the behaviour of the attackers.
Using information theory, digital networks are able to reconstruct signals despite noise. By modelling correct decisions as a signal, and attacks as noise, we have proven in previous work that typically, information is carried in ratings. With techniques similar to those applied in digital networks, we can reconstruct the correct decision. So, we propose a framework of methods to use information to come to correct decisions despite attacks.
Our framework consists of general techniques regarding transforming ratings to correct decisions, and of decision schemes based on these techniques. There are two major applications: a centralised system making a decision, and a decentralised system where individuals make decisions. Centralised examples are YouTube deleting content on the basis of copyright claims, Facebook censoring obscene material and finding fraudulent merchants on an e-commerce system. Decentralised example are ad-hoc networks, where distant nodes are selected to route sensitive information, peer to peer networks, with malicious peers breaking protocol, and peer assessment, where students have to grade their peers. We deliver both a centralised and a decentralised system that makes provably correct decisions under all attacks.
A major component of the framework is the theoretical foundation for ratings. We define three desirable properties: robustness, optimality and stability. A decision scheme is called epsilon-robust if it provides the wrong decision with a probability under epsilon. With sufficient ratings from sources that are sufficiently probably honest, this is easy to obtain. Optimality is about reducing the cost (amount and complexity of ratings) to the minimum. Stability means that if the degree of honesty is lower than expected, the decision scheme cannot be improved without raising costs. We investigate in which contexts robustness, optimality and stability can combine, and at which cost this occurs.
The most interesting context is dynamic: where users can determine (with a probability of false positives/negatives) the veracity of previous ratings. This dynamic context is both theoretically and practically interesting. The theoretical interest is that more advanced information theoretic techniques are required, and there may be deep links to other fields, such as adversarial machine learning. The practical interest is that in many systems, sources are being used more than once, and decision makers do have a vague idea about the quality of older ratings. Provably effective use of this dynamic information has not been achieved, and will improve the security of rating systems.
The result of this research will be to provide more secure rating systems.
Ratings are especially important in open networks, which play a large role in the internet of things. In open networks, participants are potentially malicious (attackers), yet we may rely on information that they provide. In current analysis of networks that use potentially unfair ratings, assumptions are made about the attackers. For example, that they maximise their profit, or want to perform specific actions. In reality, however, we cannot know what the attackers want or will do. This is the crucial challenge in our approach: we provide solutions with a proven risk-bound, regardless of the behaviour of the attackers.
Using information theory, digital networks are able to reconstruct signals despite noise. By modelling correct decisions as a signal, and attacks as noise, we have proven in previous work that typically, information is carried in ratings. With techniques similar to those applied in digital networks, we can reconstruct the correct decision. So, we propose a framework of methods to use information to come to correct decisions despite attacks.
Our framework consists of general techniques regarding transforming ratings to correct decisions, and of decision schemes based on these techniques. There are two major applications: a centralised system making a decision, and a decentralised system where individuals make decisions. Centralised examples are YouTube deleting content on the basis of copyright claims, Facebook censoring obscene material and finding fraudulent merchants on an e-commerce system. Decentralised example are ad-hoc networks, where distant nodes are selected to route sensitive information, peer to peer networks, with malicious peers breaking protocol, and peer assessment, where students have to grade their peers. We deliver both a centralised and a decentralised system that makes provably correct decisions under all attacks.
A major component of the framework is the theoretical foundation for ratings. We define three desirable properties: robustness, optimality and stability. A decision scheme is called epsilon-robust if it provides the wrong decision with a probability under epsilon. With sufficient ratings from sources that are sufficiently probably honest, this is easy to obtain. Optimality is about reducing the cost (amount and complexity of ratings) to the minimum. Stability means that if the degree of honesty is lower than expected, the decision scheme cannot be improved without raising costs. We investigate in which contexts robustness, optimality and stability can combine, and at which cost this occurs.
The most interesting context is dynamic: where users can determine (with a probability of false positives/negatives) the veracity of previous ratings. This dynamic context is both theoretically and practically interesting. The theoretical interest is that more advanced information theoretic techniques are required, and there may be deep links to other fields, such as adversarial machine learning. The practical interest is that in many systems, sources are being used more than once, and decision makers do have a vague idea about the quality of older ratings. Provably effective use of this dynamic information has not been achieved, and will improve the security of rating systems.
The result of this research will be to provide more secure rating systems.
Planned Impact
There are multiple ways in which our research can have a positive impact. There are commercial applications of our research, via two routes:
1. There is a direct route to commercialisation, via the systems that we deliver in case-studies (centralised and decentralised).
2. And there is an indirect route, where our results and proofs are used by other parties to improve their systems.
Finally, there are non-commercial routes to impact. We discuss these three cases below:
We construct a centralised system, which accumulates reports from users, and makes decisions based upon these. An example is YouTube's copyright claim system. It is currently under criticism, since YouTube cannot manually check all complaints. Therefore, some copyrighted content stays online too long whereas other legal content is unjustifiably removed. Both are unacceptable, and may cause legal issues for Google (YouTube's owner). Provably keeping the false decisions below a threshold epsilon also helps Google defend against litigation. YouTube is far from the only system that relies on reports from users, and since we do not use any of the domain specific properties (i.e. video's), our approach can applied to other systems (e-market places, malware detection on software distributors, malicious website detection in a browser).
We also construct a decentralised robust decision maker. Here, individuals can adopt a piece of software to ensure their own decisions are correct with bounded risk, rather than monolithic systems-wide decision making.
An example is vehicular ad-hoc networks, where moving vehicles communicate with eachother. The purpose of communication could be to relay traffic information, to warn nearby vehicles to brake, or even to (partially) automate driving.
The challenge here is that the amount of sources available is more sparse in this environment. Fortunately, domain-specific elements can be used to mitigate this problem, such as traffic information via radio or visual cues from brake lights from other vehicles.
In order to build systems that make robust decisions, we need to develop novel techniques with provable results. These results can be used outside the specific systems that we deliver. Therefore, we believe we push forward all domains that involve (secure use of) information from potentially malicious sources. Specifically, we can apply some of our results to crowdsourcing, trust management systems, trust and reputation systems, adversarial machine learning, secure routing protocols, decision making, information fusion, and the risk of using trusted third parties in security protocols. Our results enable the development of provably secure rating systems.
Part of the research performed in this research will be taught in the context of the security track of the Software Engineering Programme at the University of Oxford. The SEP is a programme for professional master students. The material will be taught to students with a career in computer security.
1. There is a direct route to commercialisation, via the systems that we deliver in case-studies (centralised and decentralised).
2. And there is an indirect route, where our results and proofs are used by other parties to improve their systems.
Finally, there are non-commercial routes to impact. We discuss these three cases below:
We construct a centralised system, which accumulates reports from users, and makes decisions based upon these. An example is YouTube's copyright claim system. It is currently under criticism, since YouTube cannot manually check all complaints. Therefore, some copyrighted content stays online too long whereas other legal content is unjustifiably removed. Both are unacceptable, and may cause legal issues for Google (YouTube's owner). Provably keeping the false decisions below a threshold epsilon also helps Google defend against litigation. YouTube is far from the only system that relies on reports from users, and since we do not use any of the domain specific properties (i.e. video's), our approach can applied to other systems (e-market places, malware detection on software distributors, malicious website detection in a browser).
We also construct a decentralised robust decision maker. Here, individuals can adopt a piece of software to ensure their own decisions are correct with bounded risk, rather than monolithic systems-wide decision making.
An example is vehicular ad-hoc networks, where moving vehicles communicate with eachother. The purpose of communication could be to relay traffic information, to warn nearby vehicles to brake, or even to (partially) automate driving.
The challenge here is that the amount of sources available is more sparse in this environment. Fortunately, domain-specific elements can be used to mitigate this problem, such as traffic information via radio or visual cues from brake lights from other vehicles.
In order to build systems that make robust decisions, we need to develop novel techniques with provable results. These results can be used outside the specific systems that we deliver. Therefore, we believe we push forward all domains that involve (secure use of) information from potentially malicious sources. Specifically, we can apply some of our results to crowdsourcing, trust management systems, trust and reputation systems, adversarial machine learning, secure routing protocols, decision making, information fusion, and the risk of using trusted third parties in security protocols. Our results enable the development of provably secure rating systems.
Part of the research performed in this research will be taught in the context of the security track of the Software Engineering Programme at the University of Oxford. The SEP is a programme for professional master students. The material will be taught to students with a career in computer security.
Organisations
Publications
| Description | The proposed theoretical foundation of the work has been developed and proven correct. In particular, we have developed a procedure that takes into account information provided by different sources to make a decision -- a decision scheme. The decision scheme assumes that the information sources are lying with some probability, and that this probability may be higher or lower, depending on the trust in the source. The challenge is to correctly weight how much more influence a source gains, if it becomes more trusted. Our proposed decision scheme is proven robust, optimal and stable in this setting. Robustness, optimality and stability are the three important properties that we set out to achieve. Robustness means that the decisions that the scheme only makes mistakes with an arbitrarily small probability epsilon. Optimality means that the scheme uses the minimal amount of ratings to do so. Finally, stability means that a small error in judging the trustworthiness of the sources only decreases robustness by a small amount. This means that the theoretical foundation is established, which represent a major part of the objectives of the project. The next objectives of the project are to apply the work on specific use cases, which is the stage that the project is about to enter. The foundation allows anyone to use information from potentially malicious sources in a more robust and secure way. Concrete examples are reports of malicious acivity (malware, copyright infringement, scams), online ratings, sensor networks, traffic reports, routing information, etc. Systems that depend on feedback from users can benefit from our approach, by being able to make provably robust decisions. If such systems make security critical decisions, then the ability to prove that these decisions are almost certainly correct is a major improvement over status quo. |
| Exploitation Route | The foundational work covers a relatively simple scenario. But up to this point, even the simple scenario was not sufficiently understood to allow for formal proofs regarding the quality of the decisions made on the basis of ratings. From an academic standpoint, our foundation opens up the possibility of theoretical extensions and generalisations, which cover increasingly complex scenarios. Practically speaking, we can already identify applications that are close to the scenarios that we have already captured formally. We will be conducting case studies to apply our techniques to copyright infringement on video platforms, as well as in the context of traffic information in vehicular networks. These approaches offer the benefit of provably robust decisions, which can be a major asset in a legal framework, and when lives are potentially at stake. There are many other examples of systems where information from potentially malicious users is used to make security critical decisions, and in principle, our approach could be applied to each of these systems -- although the actual foundation we have needs to be extended and generalised to achieve this. |
| Sectors | Communities and Social Services/Policy,Digital/Communication/Information Technologies (including Software) |