Triangle counting is essential for analyzing network structures and optimizing recommendation systems, yet it can lead to privacy breaches if individual data is not adequately protected during the analysis. Differential privacy has become a widely adopted standard to safeguard personal privacy. Current research mainly focuses on central and local models, which differ in applicability and performance. The central model cannot be applied when graph data is distributed among multiple parties without a trusted central server, while the local model provides unsatisfactory performance. In this paper, we explore a two-party scenario where each party holds private information about a group of users and is not allowed to disclose this information to the other party. We have proposed a scheme called HTTC-DPk, which ensures both differential privacy and k-anonymity, and is better suited to the constraints of the two-party setting compared to both central and local models. Our method integrates the noisy maximum degree computation for both intra-party and inter-party edges, along with the differentially private inter-party triangle counting based on two-party interactions. Additionally, we introduce an enhanced scheme HTTC-DPk* that strikes a balance between accuracy and communication costs, particularly suitable for large-scale graphs. We have provided comprehensive theoretical proof of our scheme's privacy and demonstrated through extensive experiments that our approach performs well under various cases.

Graph data analysis, particularly local triangle counting, plays a pivotal role in deciphering complex relationships within graph data. This method is invaluable across diverse fields such as social networks, transportation, and cybersecurity. However, this process often involves handling sensitive information, necessitating that the relationship between any two nodes is considered private. Differential privacy (DP) is a formal model to address privacy concerns and can be categorized into two types: the central DP (CDP) model, which achieves better result accuracy, and the local DP (LDP) model, which does not assume a trusted server. To bridge the gap between the two models, we propose Sectric, a server-aided crypto-assisted local triangle counting protocol, in this paper. It can achieve the same result accuracy with the same privacy budget as the CDP model without assuming a trusted server. Sectric also explores a new approach in crypto-assisted graph data analysis algorithms that represents a node's neighbors using a set instead of an adjacency vector, and successfully achieves higher efficiency compared to other crypto-assisted solutions. We also conduct theoretical and empirical evaluations to demonstrate that Sectric achieves the design principles.

In this article, we focus on the emerging field of web-based object detection, which has gained considerable attention due to its ability to utilize large amounts of web data for training, thus eliminating the need for labor-intensive manual annotations. However, the noisy and ever-evolving nature of web data poses challenges in preparing high-quality datasets for web-based object detection. To address these challenges, we propose a fully automatic dataset preparation method in this article. Our proposed method incorporates a hierarchical clustering module that assigns multiple precise labels to each image. This module is based on our observation that web image data exhibits different distributions at varying granularities. Furthermore, an evolutionary relabeling module ensures the adaptability of both the prepared dataset and trained detection models to the ever-evolving web data. Extensive experiments demonstrate that our method outperforms other web-based methods, and achieves a comparable performance to those manually labeled benchmark datasets.

Automatic dataset preparation can help users avoid labor-intensive and costly manual data annotations. The difficulty in preparing a high-quality dataset for object detection involves three key aspects: relevance, naturality, and balance, which are not addressed by existing works. In this paper, we leverage information from the web, and propose a fully-automatic dataset preparation mechanism without any human annotation, which can automatically prepare a high-quality training dataset for the detection task with English text terms describing target objects. It contains three key designs, i.e., keyword expansion, data de-noising, and data balancing. Our experiments demonstrate that the object detectors trained with auto-prepared data are comparable to those trained with benchmark datasets and outperform other baselines. We also demonstrate the effectiveness of our approach in several more challenging real-world object categories that are not included in the benchmark datasets.

Butterfly (a cyclic graph motif) counting is a fundamental task with many applications in graph analysis, which aims at computing the number of butterflies in a large graph. With the rapid growth of graph data, it is more and more challenging to do butterfly counting due to the super-linear time complexity and large memory consumption. In this paper, we study I/O-efficient algorithms for doing butterfly counting on hierarchical memory. Existing algorithms of the kind cannot guarantee I/O optimality. Observing that in order to count butterflies, it suffices to "witness" a subgraph instead of the whole structure, a new class of algorithms called semi-witnessing algorithm is proposed. We prove that a semi-witnessing algorithm is not restricted by the lower bound Ømega(|E|2/MB) of a witnessing algorithm, and give a new bound of Ømega(min(|E|2/MB, |E|/|V| √M B)). We further develop the IOBufs algorithm that manages to approach the I/O lower bound, and thus claim its optimality. Finally, we make efforts to parallelize IOBufs to further improve the performance and scalability. We show in the experiment that IOBufs significantly outperforms the state-of-the-art algorithms EMRC and BFC-EM. In addition, IOBufs can scale to conducting butterfly counting on the Clueweb graph with 37 billion edges and quintillions (10^18 ) of butterflies.

Android is a growing target for malicious software (malware) because of its popularity and functionality. Malware poses a serious threat to users’ privacy, money, equipment and file integrity. A series of data-driven malware detection methods were proposed. However, there exist two key challenges for these methods: (1) how to learn effective feature representation from raw data; (2) how to reduce the dependence on the prior knowledge or human labors in feature learning. Inspired by the success of deep learning methods in the feature representation learning community, we propose a malware detection framework which starts with learning rich-features by a novel unsupervised feature learning algorithm Merged Sparse Auto-Encoder (MSAE). In order to extract more compact and discriminative feature from the rich-features to further boost the malware detection capability, a hybrid deep network learning algorithm Stacked Hybrid Learning MSAE and SDAE (SHLMD) is established by further incorporating a classical deep learning method Stacked Denoising Auto-encoders (SDAE). After that, we feed the feature learned by MSAE and SHLMD respectively to classification algorithms, e.g., Support Vector Machine (SVM) or K-NearestNeighbor (KNN), to train a malware detection model. Evaluation results on two real-world datasets demonstrate that SHLMD achieves 94.46 and 90.57 percent accuracy respectively, which outperforms the classical unsupervised feature representation learning Sparse Auto-encoder (SAE). MSAE performs similarly to SAE. SHLMD can further improve the performance of MSAE and the supervised fine-tuned method SDAE. Besides, we compare the performance of our methods with that of state-of-the-art detection approaches, including classical deep-learning-based methods. Extensive experiments show that our proposed methods are effective enough to detect Android malware.

Remote data integrity checking is a crucial technology in cloud computing. Recently, many works focus on providing data dynamics and/or public verifiability to this type of protocols. Existing protocols can support both features with the help of a third-party auditor. In a previous work, Sebé et al. propose a remote data integrity checking protocol that supports data dynamics. In this paper, we adapt Sebé et al.'s protocol to support public verifiability. The proposed protocol supports public verifiability without help of a third-party auditor. In addition, the proposed protocol does not leak any private information to third-party verifiers. Through a formal analysis, we show the correctness and security of the protocol. After that, through theoretical analysis and experimental results, we demonstrate that the proposed protocol has a good performance.

Abnormal events, such as security attacks, misconfigurations, or electricity failures, could have severe consequences toward the normal operation of the Border Gateway Protocol (BGP) that is in charge of the delivery of packets between different autonomous domains, a key operation for the Internet to function. Unfortunately, it has been a difficult task for network security researchers and engineers to classify and detect these events. In our previous work, we have shown that with classification (which relies on the labeling with domain knowledge from BGP experts), it is feasible to effectively detect and distinguish some worms and blackouts from normal BGP behaviors. In this paper, we move one important step forward—we show that we can automatically detect and classify between different abnormal BGP events based on a hierarchy discovered by clustering. As a systematic application of data mining, we devise a clustering method based on normalized BGP data that forms a tree-like hierarchy of abnormal BGP event classes. We then obtain a set of classification rules for each class (node) in the hierarchy, thus able to label unknown BGP data to a closest class. Our method works even as the BGP dynamics evolve over time, as shown in our experiments with seven different abnormal events during a four-year period. Our work, in a more general context, shows it is promising to conduct an interdisciplinary research between network security and data mining in solving real-world problems.

Protection of privacy has become an important problem in data mining. In particular, individuals have become increasingly unwilling to share their data, frequently resulting in individuals either refusing to share their data or providing incorrect data. In turn, such problems in data collection can affect the success of data mining, which relies on sufficient amounts of accurate data in order to produce meaningful results. Random perturbation and randomized response techniques can provide some level of privacy in data collection, but they have an associated cost in accuracy. Cryptographic privacy-preserving data mining methods provide good privacy and accuracy properties. However, in order to be efficient, those solutions must be tailored to specific mining tasks, thereby losing generality. In this paper, we propose efficient cryptographic techniques for online data collection in which data from a large number of respondents is collected anonymously, without the help of a trusted third party. That is, our solution allows the miner to collect the original data from each respondent, but in such a way that the miner cannot link a respondent’s data to the respondent. An advantage of such a solution is that, because it does not change the actual data, its success does not depend on the underlying data mining problem. We provide proofs of the correctness and privacy of our solution, as well as experimental data that demonstrates its efficiency. We also extend our solution to tolerate certain kinds of malicious behavior of the participants. 1.

In order to protect individuals' privacy, the technique of k-anonymization has been proposed to de-associate sensitive attributes from the corresponding identifiers. In this paper, we provide privacy-enhancing methods for creating k-anonymous tables in a distributed scenario. Specifically, we consider a setting in which there is a set of customers, each of whom has a row of a table, and a miner, who wants to mine the entire table. Our objective is to design protocols that allow the miner to obtain a k-anonymous table representing the customer data, in such a way that does not reveal any extra information that can be used to link sensitive attributes to corresponding identifiers, and without requiring a central authority who has access to all the original data. We give two different formulations of this problem, with provably private solutions. Our solutions enhance the privacy of k-anonymization in the distributed scenario by maintaining end-to-end privacy from the original customer data to the final k-anonymous results.

Privacy has become an increasingly important issue in data mining. In this paper, we consider a scenario in which a data miner surveys a large number of customers to learn classification rules on their data, while the sensitive attributes of these customers need to be protected. Solutions have been proposed to address this problem using randomization techniques. Such solutions exhibit a tradeoff of accuracy and privacy: the more each customer's private information is protected, the less accurate result the miner obtains; conversely, the more accurate the result, the less privacy for the customers. In this paper, we propose a simple cryptographic approach that is efficient even in a many-customer setting, provides strong privacy for each customer, and does not lose any accuracy as the cost of privacy. Our key technical contribution is a privacy-preserving method that allows a data miner to compute frequencies of values or tuples of values in the customers’ data, without revealing the privacy-sensitive part of the data. Unlike general-purpose cryptographic protocols, this method requires no interaction between customers, and each customer only needs to send a single flow of communication to the data miner. However, we are still able to ensure that nothing about the sensitive data beyond the desired frequencies is revealed to the data miner. To illustrate the power of our approach, we use our frequency mining computation to obtain a privacy-preserving naive Bayes classifier learning algorithm. Initial experimental results demonstrate the practical efficiency of our solution. We also suggest some other applications of privacy-preserving frequency mining.