Evaluating the security of multi-agent systems (MASs) powered by large language models (LLMs) is challenging, primarily because of the systems' complex internal dynamics and the evolving nature of LLM vulnerabilities. Traditional attack graph (AG) methods often lack the specific capabilities to model attacks on LLMs. This paper introduces AI-agent application Threat assessment with Attack Graphs (ATAG), a novel framework designed to systematically analyze the security risks associated with AI-agent applications. ATAG extends the MulVAL logic-based AG generation tool with custom facts and interaction rules to accurately represent AI-agent topologies, vulnerabilities, and attack scenarios. As part of this research, we also created the LLM vulnerability database (LVD) to initiate the process of standardizing LLM vulnerabilities documentation. To demonstrate ATAG's efficacy, we applied it to two multi-agent applications. Our case studies demonstrated the framework's ability to model and generate AGs for sophisticated, multi-step attack scenarios exploiting vulnerabilities such as prompt injection, excessive agency, sensitive information disclosure, and insecure output handling across interconnected agents. ATAG is an important step toward a robust methodology and toolset to help understand, visualize, and prioritize complex attack paths in multi-agent AI systems (MAASs). It facilitates proactive identification and mitigation of AI-agent threats in multi-agent applications.

The increasing cyber threats to critical infrastructure highlight the importance of private companies and government agencies in detecting and sharing information about threat activities. Although the need for improved threat information sharing is widely recognized, various technical and organizational challenges persist, hindering effective collaboration. In this study, we review the challenges that disturb the sharing of usable threat information to critical infrastructure operators within the industrial control system (ICS) domain. We analyze three major incidents: Stuxnet, Industroyer, and Triton. In addition, we perform a systematic analysis of 196 procedure examples across 79 ATT&CK® techniques from 22 ICS-related malware families, utilizing automated natural language processing techniques to systematically extract and categorize threat observables. Additionally, we investigated nine recent ICS vulnerability advisories from the CISA Known Exploitable Vulnerability catalog. Our analysis identified four important limitations in the ICS threat information sharing ecosystem: (i) the lack of coherent representation of artifacts related to ICS adversarial techniques in information sharing language standards (e.g., STIX); (ii) the dependence on undocumented proprietary technologies; (iii) limited technical details provided in vulnerability and threat incident reports; and (iv) the accessibility of technical details for observed adversarial techniques. This study aims to guide the development of future information-sharing standards, including the enhancement of the cyber-observable objects schema in STIX, to ensure accurate representation of artifacts specific to ICS environments.

Logical attack graphs (LAGs) are used to analyze non-trivial relationships between organizational assets and vulnerabilities for cybersecurity risk assessment in complex computerized environments. They help identify dangerous attack scenarios that extend beyond the immediate impact of vulnerability exploitations. In this article, we focus on MulVAL, one of the most popular open-source LAG frameworks. The expressiveness and extensibility of LAG frameworks allow the addition of new attack scenarios in the form of logical interaction rules. However, the existing set of rules developed for MulVAL covers just 20% of the adversarial techniques listed in the MITRE ATT&CK knowledge base. Furthermore, due to the absence of common coding conventions, the previously proposed interaction rules could not be incorporated into one unified library. In this paper, we define uniform coding conventions based on an ontology proposed by Iannacone et al. and incorporate 351 interaction rules identified in the literature into one comprehensive library supported by a software tool for exploring and managing the interaction rules. Further, we propose a methodology and a semi-automated framework for developing new interaction rules to fill the gap in MITRE ATT&CK coverage and demonstrate them using techniques associated with the MITRE Engenuity ATT&CK Evaluations APT29 scenario.

Human error remains the primary vector for privacy breaches, with users frequently exposing sensitive personal data through unsafe behaviors, such as granting excessive permissions, neglecting screen locks, or falling for social engineering. Yet, existing information security awareness (ISA) programs often adopt a one-size-fits-all approach, neglecting users’ personality traits and risk perception. In this work, we conducted a comprehensive five-week study with 105 participants to evaluate how personality traits and Passive Risk-Taking (PRT) interact with different ISA training methodologies. Prior research has primarily examined direct associations between personality traits and self-reported ISA measures, producing mixed findings and providing limited insight into how individual differences shape responsiveness to ISA training interventions. To address these limitations, we used a longitudinal sensor-based framework that captures real-world security behaviors over time, enabling a more reliable assessment of ISA training outcomes. Our results show that individual differences moderate training efficacy: users with high Agreeableness achieved greater gains through active-risk training (social engineering simulations), whereas those with lower Agreeableness benefited more from passive-risk training targeting omission-based risks. Furthermore, we find that Agreeableness moderates the relationships between both baseline PRT and changes in PRT and subsequent ISA improvements, while Conscientiousness moderates how resource-related PRT translates into ISA gains. Overall, these findings show that personality traits shape how users benefit from different training strategies and influence the alignment between risk reduction and awareness gains, supporting a shift toward adaptive, privacy-enhancing ISA training.

Maor Reuben, Ortal Slobodin, Idan-Chaim Cohen, Aviad Elyashar, Orna Braun-Lewensohn, Odeya Cohen, Rami Puzis. Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2025.

The scale and dynamic nature of the Web makes real-time detection of misinformation an extremely difficult task. Prior research mostly focused on offline (retrospective) detection of stories or claims using linguistic features of the content, flagging by users, and crowdsourced labels. Here, we develop a novel machine-learning methodology for detecting fake news sources using active learning, and examine the contribution of network, audience, and text features to the model accuracy. Importantly, we evaluate performance in both offline and online settings, mimicking the strategic choices fact-checkers have to make in practice as news sources emerge over time. We find that exposure networks provide information on considerably more sources than sharing networks (+49.6%), and that the inclusion of exposure features greatly improves classification PR-AUC in both offline (+33%) and online (+69.2%) settings. Textual features perform best in offline settings, but their performance deteriorates by 12.0-18.7% in online settings. Finally, the results show that a few iterations of active learning are sufficient for our model to attain predictive performance to comparable exhaustive labeling while incurring only 24.7% of the labeling costs. These results stress the importance of exposure networks as a source of valuable information for the investigation of information dissemination in social networks and question the robustness of textual features.

User feedback is one of the most effective methods to build and maintain trust in electronic commerce platforms. Unfortunately, dishonest sellers often bend over backward to manipulate users’ feedback or place phony bids in order to increase their own sales and harm competitors. The black market of user feedback, supported by a plethora of shill bidders, prospers on top of legitimate electronic commerce. In this paper, we investigate the ecosystem of shill bidders based on large-scale data by analyzing hundreds of millions of users who performed billions of transactions, and we propose a machine-learning-based method for identifying communities of users that methodically provide dishonest feedback. Our results show that (1) shill bidders can be identified with high precision based on their transaction and feedback statistics; and (2) in contrast to legitimate buyers and sellers, shill bidders form cliques to support each other.

Vehicular ad hoc network (VANET) is an emerging technology with a promising future and great challenges. It aims to promote safe driving, improve traffic flow and also enables a variety of entertainment applications. A fundamental need in such a network is the ability to assess vehicular speed. This enables the collection of statistics for the purpose of traffic engineering and long-term planning, and is also critical information for law enforcement groups. Many existing speed assessment technologies suffer from high physical visibility, and relatively expensive hardware. Even those that avoid detection, are inflexible due to being location specific. Therefore, reducing the ability to track and enforce traffic speed and limiting the collection of statistics for traffic engineering. In this paper, we propose a method for vehicle speed assessment, by extracting an induced Communication Connectivity Graph (CCG) from VANET optimized link state routing (OLSR) protocol, and composing an optimization problem for assessing the speed boundaries, using graph hop distance based constraints. We performed evaluation experiments in different traffic scenarios using traffic simulation tool. Our method can provide a cost-effective, easy to implement and hard to uncover solution for vehicles speed assessment on highways.

Abstract Sample compression using 𝜖-net effectively reduces the number of labeled instances required for accurate classification with nearest neighbor algorithms. However, one-shot construction of an 𝜖-net can be extremely challenging in large-scale distributed data sets. We explore two approaches for distributed sample compression: one where local 𝜖-net is constructed for each data partition and then merged during an aggregation phase, and one where a single backbone of an 𝜖-net is constructed from one partition and aggregates target label distributions from other partitions. Both approaches are applied to the problem of malware detection in a complex, real-world data set of Android apps using the nearest neighbor algorithm. Examination of the compression rate, computational efficiency, and predictive power shows that a single backbone of an 𝜖-net attains favorable performance while achieving a compression rate of 99%.

Cyber threat intelligence on past attacks may help with attack reconstruction and the prediction of the course of an ongoing attack by providing deeper understanding of the tools and attack patterns used by attackers. Therefore, cyber security analysts employ threat intelligence, alert correlations, machine learning, and advanced visualizations in order to produce sound attack hypotheses. In this article, we present AttackDB, a multi-level threat knowledge base that combines data from multiple threat intelligence sources to associate high-level ATT&CK techniques with low-level telemetry found in behavioral malware reports. We also present the Attack Hypothesis Generator which relies on knowledge graph traversal algorithms and a variety of link prediction methods to automatically infer ATT&CK techniques from a set of observable artifacts. Results of experiments performed with 53K VirusTotal reports indicate that the proposed algorithms employed by the Attack Hypothesis Generator are able to produce accurate adversarial technique hypotheses with a mean average precision greater than 0.5 and area under the receiver operating characteristic curve of over 0.8 when it is implemented on the basis of AttackDB. The presented toolkit will help analysts to improve the accuracy of attack hypotheses and to automate the attack hypothesis generation process.

Threat hunting relies on cyber threat intelligence to perform active hunting of prospective attacks instead of waiting for an attack to trigger some pre-configured alerts. One of the most important aspects of threat hunting is automation, especially when it concerns targeted data collection. Multi-armed bandits (MAB) is a family of problems that can be used to optimize the targeted data collection and balance between exploration and exploitation of the collected data. Unfortunately, state-of-the-art policies for solving MAB with dependent arms do not utilize the detailed interrelationships between attacks such as telemetry or artifacts shared by multiple attacks. We propose new policies, one of which is theoretically proven, to prioritize the investigated attacks during targeted data collection. Experiments with real data extracted from VirusTotal behavior reports show the superiority of the proposed techniques and their robustness in presence of noise.

The ubiquity of Network Address Translation (NAT) and mobile hotspots that aggregate source IP addresses of connected devices to a single IP address makes it difficult for an observer in the Internet to learn anything about the internal network. The IP Identification header field of Domain Name System requests and the TCP Timestamp (TCP TS) header field of TCP SYN packets are the main features for counting devices in the internal network and association of packets to these devices, also known as DeNATing. This paper introduces a new method that relies on polynomial least-squares curve fitting for DeNATing. Evaluation of our model is performed on multiple real-world datasets containing Windows and Unix devices behind a router using NAT and a mobile hotspot. The proposed method outperforms other state-of-the-art methods for all of the used datasets on all types of devices. Successful DeNATing may help in cybersecurity, anti-fraud, and other use cases.

Social distancing is an effective population-level mitigation strategy to prevent COVID19 propagation but it does not reduce the number of susceptible individuals and bears severe social consequences-a dire situation that can be overcome with the recently developed vaccines. Although a combination of these interventions should provide greater benefits than their isolated deployment, a mechanistic understanding of the interplay between them is missing. To tackle this challenge we developed an age-structured deterministic model in which vaccines are deployed during the pandemic to individuals who do not show symptoms. The model allows for flexible and dynamic prioritization strategies with shifts between target groups. We find a strong interaction between social distancing and vaccination in their effect on the proportion of hospitalizations. In particular, prioritizing vaccines to elderly (60+) before adults (20-59) is more effective when social distancing is applied to adults or uniformly. In addition, the temporal reproductive number Rt is only affected by vaccines when deployed at sufficiently high rates and in tandem with social distancing. Finally, the same reduction in hospitalization can be achieved via different combination of strategies, giving decision makers flexibility in choosing public health policies. Our study provides insights into the factors that affect vaccination success and provides methodology to test different intervention strategies in a way that will align with ethical guidelines.

Large content providers and content distribution network operators usually connect with large Internet service providers (eyeball networks) through dedicated private peering. The capacity of these private network interconnects is provisioned to match the volume of the real content demand by the users. Unfortunately, in cases in which there is a surge in traffic demand, (e.g., due to trending content or massive software updates) the capacity of the private interconnect may deplete, requiring the content provider/distributor to reroute the excess traffic through transit providers. Although such overflow events are rare, they negatively impact content providers, Internet service providers, and end-users. Such impact includes unexpected delays and disruptions that reduce the quality of the user experience, as well as direct costs paid by the Internet service provider to the transit providers. In this article, we examine the problem of predicting an overflow event in order to enable content and Internet service providers to handle the excess traffic in a timely manner. We propose an ensemble of deep learning models trained to predict overflow events over a short-term horizon of 2–4 hours and predict the specific interconnections through which the excess traffic will enter the Internet service provider. Evaluated with 2.5 years (2017-2019) of traffic measurement data from a large European Internet service provider, the models were shown to successfully recall 65% of the events with precision of 51% on average. While the lockdowns imposed by the COVID-19 pandemic reduced the overflow prediction accuracy, the pandemic’s impact on the accuracy was temporary. Although the lockdown continued on and off, the performance of models trained before the pandemic regained their performance during April-May 2020.

Information security awareness (ISA) is a practice focused on the set of skills which help a user successfully mitigate social engineering (SE) attacks. Evaluating the ISA of users is crucial, since early identification of users who are more vulnerable to SE attacks improves system security. Previous studies for evaluating the ISA of smartphone users rely on subjective data sources (questionnaires) and do not address the differences between classes of SE attacks. This paper presents a framework for evaluating the ISA of smartphone users for specific attack classes. In addition to questionnaires, we utilize objective data sources: a mobile agent, a network traffic monitor, and cybersecurity challenges. We evaluated the framework by conducting a long-term user study involving 162 users. The results show that: the self-reported behavior of users differs significantly from their actual behavior and the ISA level derived from the actual behavior of users is highly correlated with their ability to mitigate SE attacks.

Online social networks (OSNs) are ubiquitous attracting millions of users all over the world. Being a popular communication media OSNs are exploited in a variety of cyber-attacks. In this article, we discuss the chameleon attack technique, a new type of OSN-based trickery where malicious posts and profiles change the way they are displayed to OSN users to conceal themselves before the attack or avoid detection. Using this technique, adversaries can, for example, avoid censorship by concealing true content when it is about to be inspected; acquire social capital to promote new content while piggybacking a trending one; cause embarrassment and serious reputation damage by tricking a victim to like, retweet, or comment a message that he wouldn’t normally do without any indication for the trickery within the OSN. An experiment performed with closed Facebook groups of sports fans shows that (1) chameleon pages can pass by the moderation filters by changing the way their posts are displayed and (2) moderators do not distinguish between regular and chameleon pages. We list the OSN weaknesses that facilitate the chameleon attack and propose a set of mitigation guidelines.

Many tasks executed in dynamic distributed systems, such as sensor networks or enterprise environments with bring-your-own-device policy, require central coordination by a leader node. In the past it has been proven that distributed leader election in dynamic environments with constant changes and asynchronous communication is not possible. Thus, state-of-the-art leader election algorithms are not applicable in asynchronous environments with constant network changes. Some algorithms converge only after the network stabilizes (an unrealistic requirement in many dynamic environments). Other algorithms reach consensus in the presence of network changes but require a global clock or some level of communication synchrony. Determining the weakest assumptions, under which bounded leader election is possible, remains an unresolved problem. In this study we present a leader election algorithm that operates in the presence of changes and under weak (realistic) assumptions regarding message delays and regarding the clock drifts of the distributed nodes. The proposed algorithm is self-sufficient, easy to implement and can be extended to support multiple regions, self-stabilization, and mobile ad-hoc networks. We prove the algorithm's correctness and provide a complexity analysis of the time, space, and number of messages required to elect a leader.

The task of attack attribution, i.e., identifying the entity responsible for an attack, is complicated and usually requires the involvement of an experienced security expert. Prior attempts to automate attack attribution apply various machine learning techniques on features extracted from the malware's code and behavior in order to identify other similar malware whose authors are known. However, the same malware can be reused by multiple actors, and the actor who performed an attack using a malware might differ from the malware's author. Moreover, information collected during an incident may contain many clues about the identity of the attacker in addition to the malware used. In this paper, we propose a method of attack attribution based on textual analysis of threat intelligence reports, using state of the art algorithms and models from the fields of machine learning and natural language processing (NLP). We have developed a new text representation algorithm which captures the context of the words and requires minimal feature engineering. Our approach relies on vector space representation of incident reports derived from a small collection of labeled reports and a large corpus of general security literature. Both datasets have been made available to the research community. Experimental results show that the proposed representation can attribute attacks more accurately than the baselines' representations. In addition, we show how the proposed approach can be used to identify novel previously unseen threat actors and identify similarities between known threat actors.

The Internet of things (IoT) has become an integral part of our life at both work and home. However, these IoT devices are prone to vulnerability exploits due to their low cost, low resources, the diversity of vendors, and proprietary firmware. Moreover, short range communication protocols (e.g., Bluetooth or ZigBee) open additional opportunities for the lateral movement of an attacker within an organization. Thus, the type and location of IoT devices may significantly change the level of network security of the organizational network. In this paper, we quantify the level of network security based on an augmented attack graph analysis that accounts for the physical location of IoT devices and their communication capabilities. We use the depth-first branch and bound (DFBnB) heuristic search algorithm to solve two optimization problems: Full Deployment with Minimal Risk (FDMR) and Maximal Utility without Risk Deterioration (MURD). An admissible heuristic is proposed to accelerate the search. The proposed method is evaluated using a real network with simulated deployment of IoT devices. The results demonstrate (1) the contribution of the augmented attack graphs to quantifying the impact of IoT devices deployed within the organization on security, and (2) the effectiveness of the optimized IoT deployment.

One of the most effective approaches for detecting malicious activity in online social networks (OSNs) involves the use of social network honeypots - artificial profiles. Therefore, there is a growing need for the ability to reliably generate realistic artificial honeypot profiles in OSNs. In this research we present `ProfileGen' - a method for the automated generation of profiles for professional social networks, giving particular attention to producing realistic education and employment records. `ProfileGen' creates honeypot profiles that are similar to actual data by extrapolating the characteristics and properties of real data items. Evaluation by 70 domain experts confirms the method's ability to generate realistic artificial profiles that are indistinguishable from real profiles, demonstrating that our method can be applied to generate realistic artificial profiles for a wide range of applications.

Network Alignment (NA) is a generalization of the graph isomorphism problem for non-isomorphic graphs, where the goal is to find a node mapping as close as possible to isomorphism. Recent successful NA algorithms follow a search-based approach, such as simulated annealing. We propose to speed up search-based NA algorithms by pruning the search-space based on heuristic rules derived from the topological features of the aligned nodes. We define several desirable properties of such pruning rules, analyze them theoretically, and propose a pruning rule based on nodes' degrees. Experimental results show that using the proposed rule yields significant speedup and higher alignment quality compared to the state of the art. In addition, we redefine common NA objective functions in terms of established statistical analysis metrics, opening a wide range of possible objective functions.

In this paper, we propose an approach for estimating the authenticity of online discussions based on the similarity of online social media (OSM) accounts participating in the online discussion to known abusers and legitimate accounts. Our method uses similarity functions for the analysis and classification of OSM accounts. The proposed methods are demonstrated using Twitter data collected for this study and a previously published Arabic Honeypot dataset. The data collected during this study includes manually labeled accounts and a ground truth collection of abusers from crowdturfing platforms. Demonstration of the discussion topic's authenticity, derived from account similarity functions, shows that the suggested approach is effective for discriminating between topics that were strongly promoted by abusers and topics that attracted authentic public interest.

Reconnaissance is the initial and essential phase of a successful advanced persistent threat (APT). In many cases, attackers collect information from social media, such as professional social networks. This information is used to select members that can be exploited to penetrate the organization. Detecting such reconnaissance activity is extremely hard because it is performed outside the organization premises. In this paper, we propose a framework for management of social network honeypots to aid in detection of APTs at the reconnaissance phase. We discuss the challenges that such a framework faces, describe its main components, and present a case study based on the results of a field trial conducted with the cooperation of a large European organization. In the case study, we analyze the deployment process of the social network honeypots and their maintenance in real social networks. The honeypot profiles were successfully assimilated into the organizational social network and received suspicious friend requests and mail messages that revealed basic indications of a potential forthcoming attack. In addition, we explore the behavior of employees in professional social networks, and their resilience and vulnerability toward social network infiltration.

Traffic diversion through powerful cloud-based scrubbing centers provides a solution for protecting against various DDoS attacks. In one respect, such a solution enables sanitizing attack traffic close to its source and saves precious resources for the network service provider. Contrarily, the diversion of the inspected traffic toward the scrubbing centers may increase its footprint in the network. The location of the scrubbing centers greatly affects the network resource utilization and, therefore, should be carefully considered in the design of the security service. In this paper, we investigate four deployment strategies and compare their performance on a network of Points-of-Presence and on several router level topologies obtained from the RocketFuel project. The deployment quality was measured using the following criteria: the footprint of the inspected traffic, the redistribution of load on the links, and the increase in communication latency. Our results show that the deployment strategy that is considered to perform well for locating network monitors by maximizing flow coverage results in the worst footprint when traffic diversion is employed. Overall, we show that the deployment strategy that is tailored for traffic filtering is also suitable for traffic monitoring, but not the other way around.

Online social networks are a popular and important channel for people to share, find and disseminate information on a massive scale. Some of the information exposed through these networks is meant to be private. However, sensitive organizational information can be accidentally leaked by employees and become exposed to adversaries or competitors. The threat is escalated due to socialbots used by adversaries to penetrate the informal social network of an organization's employees in order to harvest sensitive information. This study evaluates the ability of an attacker to harvest leaked information using socialbots versus the effort required to wire the profiles into the organizational network. The evaluation is performed using real information diffusion data of two social networks and extensive simulations of socialbot wiring strategies. Our results demonstrate that organizations whose social network topologies are characterized by low clustering coefficient are more vulnerable to eavesdropping. We also show that the most effective socialbot wiring strategy for harvesting information is different from the most effective strategies for infiltrating the organization.

In this paper we perform cost-effectiveness analysis of strategies for monitoring the organizational social network in order to trap the attacker's profiles. We analyze attack strategies with different levels of knowledge on the employed monitoring strategies. The results demonstrate the efficacy in detecting the less sophisticated attackers and slowing down attackers that deliberately avoid the profiles being monitored.

Monte-Carlo Tree Search (MCTS) algorithms estimate the value of MDP states based on rewards received by performing multiple random simulations. MCTS algorithms can use different strategies to aggregate these rewards and provide an estimation for the states’ values. The most common aggregation method is to store the mean reward of all simulations. Another common approach stores the best observed reward from each state. Both of these methods have complementary benefits and drawbacks. In this paper, we show that both of these methods are biased estimators for the real expected value of MDP states. We propose an hybrid approach that uses the best reward for states with low noise, and otherwise uses the mean. Experimental results on the Sailing MDP domain show that our method has a considerable advantage when the rewards are drawn from a noisy distribution.

Snake in the Box (SIB) is the problem of finding the longest simple path along the edges of an n-dimensional cube, subject to certain constraints. SIB has important applications in coding theory and communications. State of the art algorithms for solving SIB apply uninformed search with symmetry breaking techniques. We formalize this problem as a search problem and propose several admissible heuristics to solve it. Using the proposed heuristics is shown to have a huge impact on the number of nodes expanded and, in some configurations, on runtime. These results encourage further research in using heuristic search to solve SIB, and to solve maximization problems more generally.

The Target Oriented Network Intelligence Collection (TONIC) problem is the problem of finding profiles in a social network that contain publicly available information about a given target profile via automated crawling. Such profiles are called leads. Leads can be found by crawling the network using the profiles' friend lists (immediate neighborhood) in order to decide which profile will be crawled next. Assuming that leads tend to cluster together, prior work limited the search for new leads only to immediate neighbors of the leads previously found. In this paper we relax this limitation, and extend the scope of the search to a wider neighborhood, including the possibility of crawling to non-leads, i.e., profiles that have no publicly available information about the target. We propose a set of heuristics that guide this search. Experimental results show that with the new setting more leads can be found and leads are found faster. In addition, we perform a cost benefit analysis of the search, weighing the reward of finding leads with the costs of the search.

Most work in heuristic search considers problems where a low cost solution is preferred (MIN problems). In this paper, we investigate the complementary setting where a solution of high reward is preferred (MAX problems). Example MAX problems include finding the longest simple path in a graph, maximal coverage, and various constraint optimization problems. We examine several popular search algorithms for MIN problems — optimal, suboptimal, and bounded suboptimal - and discover the curious ways in which they misbehave on MAX problems. We propose modifications that preserve the original intentions behind the algorithms but allow them to solve MAX problems, and compare them theoretically and empirically. Interesting results include the failure of bidirectional search and a discovered close relationships between Dijkstra's algorithm, weighted A*, and depth-first search. This work demonstrates that MAX problems demand their own heuristic search algorithms, which are worthy objects of study in their own right.

In this paper we introduce the Target Oriented Network Intelligence Collection (TONIC) problem, which is the problem of finding profiles in a social network that contain information about a given target via automated crawling. We formalize TONIC as a search problem and a best-first approach is proposed for solving it.Several heuristics are presented to guide this search.These heuristics are based on the topology of the currently known part of the social network.The efficiency of the proposed heuristics and the effect of the graph topology on their performance is experimentally evaluated on the Google+ social network.

The Web is far less usable and accessible for people with vision impairments than it is for sighted people. Web automation, a process of automating browsing actions on behalf of the user, has the potential to bridge the divide between the ways sighted and people with vision impairment access the Web; specifically, it can enable the latter to breeze through web browsing tasks that beforehand were slow, hard, or even impossible to accomplish. Typical web automation requires that the user record a macro, a sequence of browsing steps, so that these steps can be automated in the future by replaying the macro. However, for people with vision impairment, automation with macros is not usable.

Online social networking sites have become increasingly popular over the last few years. As a result, new interdisciplinary research directions have emerged in which social network analysis methods are applied to networks containing hundreds of millions of users. Unfortunately, links between individuals may be missing either due to an imperfect acquirement process or because they are not yet reflected in the online network (i.e., friends in the real world did not form a virtual connection). The primary bottleneck in link prediction techniques is extracting the structural features required for classifying links. In this article, we propose a set of simple, easy-to-compute structural features that can be analyzed to identify missing links. We show that by using simple structural features, a machine learning classifier can successfully identify missing links, even when applied to a predicament of classifying links between individuals with at least one common friend. We also present a method for calculating the amount of data needed in order to build more accurate classifiers. The new Friends measure and Same community features we developed are shown to be good predictors for missing links. An evaluation experiment was performed on ten large social networks datasets: Academia.edu, DBLP, Facebook, Flickr, Flixster, Google+, Gowalla, TheMarker, Twitter, and YouTube. Our methods can provide social network site operators with the capability of helping users to find known, offline contacts and to discover new friends online. They may also be used for exposing hidden links in online social networks.

Effective deployment of Real Time Distributed Network Intrusion Detection Systems (DNIDS) on High- speed and large-scale networks within limited budget constraints is a challenging task. In this paper we investigate algorithms aiming at optimizing the deployment of DNIDS systems. We use Group Betweenness Centrality (GBC) as an approximation of the DNIDS deployment utility. In this work we use two cost models. The first cost model assumes that all network intrusion detection devices have the same cost. The second model assumes that the cost of the device is relative to the traffic load on the network node on which it is installed. We evaluate two algorithms for finding the most prominent group in these cost models. The first algorithm is based on greedy choice of vertices and the second is based on heuristic search and finds the optimal deployment locations. We investigate combinations of heuristic functions based on solution cost and on solution utility and different node ordering strategies. We show that intelligent choice of the heuristic functions and node ordering can speed up the search. Empirical evaluation shows that while in the first cost model the greedy algorithm produces results that are negligibly close to optimal in the second cost model the difference between optimal and suboptimal solutions can be significant.

In this paper we explore a novel approach for anytime heuristic search, in which the node that is most probable to improve the incumbent solution is expanded first. This is especially suited for the "anytime aspect" of anytime algorithms - the possibility that the algorithm will be be halted anytime throughout the search. The potential of a node to improve the incumbent solution is estimated by a custom cost function, resulting in Potential Search, an anytime best-first search. Experimental results on the 15-puzzle and on the key player problem in communication networks (KPP-COM) show that this approach is competitive with state-of-the-art anytime heuristic search algorithms, and is more robust.

Betweenness-Centrality measure is often used in social and computer communication networks to estimate the potential monitoring and control capabilities a vertex may have on data flowing in the network. In this article, we define the Routing Betweenness Centrality (RBC) measure that generalizes previously well known Betweenness measures such as the Shortest Path Betweenness, Flow Betweenness, and Traffic Load Centrality by considering network flows created by arbitrary loop-free routing strategies. We present algorithms for computing RBC of all the individual vertices in the network and algorithms for computing the RBC of a given group of vertices, where the RBC of a group of vertices represents their potential to collaboratively monitor and control data flows in the network. Two types of collaborations are considered: (i) conjunctive—the group is a sequences of vertices controlling traffic where all members of the sequence process the traffic in the order defined by the sequence and (ii) disjunctive—the group is a set of vertices controlling traffic where at least one member of the set processes the traffic. The algorithms presented in this paper also take into consideration different sampling rates of network monitors, accommodate arbitrary communication patterns between the vertices (traffic matrices), and can be applied to groups consisting of vertices and/or edges. For the cases of routing strategies that depend on both the source and the target of the message, we present algorithms with time complexity of O ( n 2 m ) where n is the number of vertices in the network and m is the number of edges in the routing tree (or the routing directed acyclic graph (DAG) for the cases of multi-path routing strategies). The time complexity can be reduced by an order of n if we assume that the routing decisions depend solely on the target of the messages. Finally, we show that a preprocessing of O ( n 2 m ) time, supports computations of RBC of sequences in O ( kn ) time and computations of RBC of sets in O ( n 3 n ) time, where k in the number of vertices in the sequence or the set.

Threats such as computer worms, Spyware and Trojans account for more than 10% of the total traffic of a network service providers (NSP). The NSP traffic can be monitored and cleaned by distributed network intrusion detection system (DNIDS) that may be deployed on the NSP routers/links. In this study we choose which routers/links to protect based on group betweenness centrality index that is used as a measure of their collaborative influence on the communication in the NSP infrastructure. During the current study we developed a framework aimed at slowing down or even preventing the propagation of known threats. In the first part of the framework the influential group of routers/links has to be located. In the second part we analyze parallel propagation of multiple types of threats in the NSP infrastructure using the susceptible infective removed model of epidemic propagation.

Internet users form social networks as they communicate with each other. Computer worms and viruses exploit these social networks in order to propagate to other users. In this paper we present a new framework aimed at slowing down or even preventing the propagation of computer worms and viruses in social networks. In the first part of the framework a social network has to be derived for a given community of users. In the second part the group of users that have the highest influence on the communication in the social network has to be located. The group betweenness centrality measure is used to evaluate the influence of each candidate group. In the third part we analyze the threat propagation in the social network assuming that a distributed network intrusion detection system (DNIDS) is monitoring the traffic of the group. The analysis is performed using a network simulator that was developed for this purpose. In the fourth part a DNIDS has to be deployed on a range of ISPs in order to monitor and clean the traffic of the users belonging to the central group. We applied the new framework by deriving the social network of 1000 students, finding the most influential group of users, and analyzing the influence of the deployment of DNIDS using a simulation tool. The simulation results demonstrated the framework's ability to slow down or even prevent the propagation of threats by cleaning the traffic of central group of users.