Malicious Agents and the Power of the Few : On the Logic of Abnormality in Social Networks

Abstract

Denne avhandlingen befinner seg i skjæringspunktet mellom formallogikk, samfunnsvitenskap, informasjonsvitenskap og forskning innenfor kunstig intelligens. Den er viet til studiet av agenter i multiagent-systemer som oppfører seg unormalt eller ondsinnet for sin egen vinning. Ved å analysere slike agenter får vi ikke bare nyttig informasjon om den potensielle skaden slike agenter kan utgjøre, men også om sikkerheten til systemene de befinner seg i. Helt spesifikt bruker vi sosiale nettverkslogikker til å resonnere rundt ondsinnet og unormal oppførsel. Sosiale nettverkslogikker er logiske systemer der et sosialt nettverk av relaterte agenter er eksplisitt representert. Selv om en sosial nettverkslogikk ikke nødvendigvis er basert på modallogikk, vil alle de logiske systemene presentert i denne avhandlingen være det.

Fire forskjellige sosial nettverkslogikk-formaliseringer av ondsinnet og unormal oppførsel blir gitt. I den første bygger vi en temporallogikk for å representere oppførsel forbundet med sosiale bots, som er dataprogrammer som oppfører seg som menneskelige brukere på sosiale medier. De logiske modellene følger et sosialt nettverk slik det utvikler seg over tid gjennom en lineær tidslinje. Vi foreslår å bruke modellsjekking til å avsløre om og hvis så, når, det har vært sosial bot-oppførsel i nettverket. En modellsjekkingsalgoritme blir presentert og det vises at modellsjekkingsproblemet kan løses i polynomisk tid. Deretter utvider vi logikken med elementer fra hybridlogikk. Med denne utvidede logikken kan vi bruke modelsjekking til ikke bare å avsløre om og når, men også hvem som har oppført seg som en sosial bot. Denne modellsjekkingsalgoritmen bruker polynomisk plass.

I den andre formaliseringen ser vi på et sosialt nettverk der agenter kan legge ut og dele informasjon--og viser hvordan en agent i systemet kan utnytte nettverksstrukturen til nå mange agenter med kontroversiell informasjon. For å granske slike situasjoner presenterer vi et logisk system med dynamiske og strategiske utvidelser. Motivert av å analysere sikkerhet og mulig misbruk i systemet vårt, bruker vi en teknikk kjent som kvantifisering over handlinger. Vi bruker denne teknikken for å studere taktiske handlinger fra perspektivet til agenten.

I de tredje og fjerde formaliseringene utvider vi logikker kjent fra litteraturen for å analysere handlingsrommet til ondsinnede og unormale agenter i eksisterende systemer. Den tredje formaliseringen bygger på eksisterende forskning om en nettverksstruktur som kalles strukturell balanse. I denne konteksten introduserer vi nye operatorer for å undersøke effekten av forandringer der vennskap blir til fiendskap, og omvendt. Med disse operatorene kan vi studere situasjoner hvor agenter alene kan ha makt til å endre en global nettverksstruktur. Den fjerde formaliseringen utforsker en ny type agent i en eksisterende modell for terskel-begrenset diffusjon. I denne modellen er det typisk slik at agenter tilegner seg en oppførsel eller en mening når et gitt antall av naboene deres har antatt den. Dette antallet er bestemt av en gitt terskelverdi. Inspirert av kjente arbeider om forskjellige agenttyper, diskuterer vi hva det kan bety å innlemme en ondsinnet eller en unormal agent i diffusjonsprosesssen. Resultatet er en agent som ved oppnådd terskelverdi kan kansellere andre agenters innflytelse.

Med denne avhandlingen motiverer vi bruken av logikk som et unikt og verdifullt formalt verktøy for å analysere sosiale fenomener. Vi viser også at formale beskrivelser av ondsinnede agenter kan legge grunnlaget for å bekjempe dem. Forhåpentligvis vil denne avhandlingen oppfordre til videre forskning på ondsinnede og unormale agenter med sosial nettverkslogikk.

This thesis is situated at the intersection of formal logic, social science, information science and artificial intelligence research. It is devoted to the study of agents in multi-agent systems who act out of the ordinary or maliciously for their own gain. Analyzing these types of agents cannot only give us valuable information about their potential power to disrupt, but also about the safety of the systems in which they act. Specifically, we use social network logics to reason about malicious and abnormal behavior. Social network logics are logical systems in which a social network of connected agents is explicitly modeled. Although a social network logic is not necessarily based on modal logic, all logical systems presented in this thesis are.

Four formal studies into malicious and abnormal behavior with social network logic are given. In the first, we build a temporal logic to model behavior associated with social bots, which are computer programs that act like human users on social media platforms. The logical models follow a social network as it evolves through a linear timeline. We propose to use model checking to detect whether, and if so, when there was social bot behavior in the network. A model checking algorithm is presented and it is shown that it runs in polynomial time. Then, we extend the logic with elements from hybrid logic. With this extended logic, model checking amounts to detecting not only whether and when, but also who in the network exhibited bot behavior. This model checking algorithm uses polynomial space.

In the second study, we look at a social network where agents can post and share information—and show how an agent within the system can take advantage of the network construction to reach many agents with a controversial opinion. To examine such situations we present a logical system with dynamic and strategic extensions. Motivated by analyzing safety and possible exploitation in our system, we rely on a technique known as quantification over actions. We use this to formally study tactical actions from an agent's perspective.

In the third and fourth studies, we extend logics from the literature to analyze the power of malicious and abnormal agents in existing systems. The third study builds on work on a particular network structure called structural balance. In this context we introduce new operators to view effects of friendships changing to enmities and vice versa. With these operators we can examine situations where single agents have the power to alter a global network structure. The fourth study explores a new type of agent in an existing model of threshold-limited influence. In this model, agents typically adopt a behavior or an opinion when a given number of their neighbors have adopted it, with respect to a given threshold. Inspired by existing work on different agent types, we discuss what it could mean to insert a malicious or abnormal agent into the diffusion. The result is an agent who when reaching the threshold can cancel out other agents' influence.

With this thesis, we motivate logic as a unique and valuable formal tool to analyze social phenomena. We also show that formal characterizations of malicious agents can lay the groundwork for combatting them. Hopefully, this thesis will encourage further research on malicious and abnormal agents with social network logic.