-
A Lower bound for Secure Domination Number of an Outerplanar Graph
Authors:
Toru Araki
Abstract:
A subset $S$ of vertices in a graph $G$ is a secure dominating set of $G$ if $S$ is a dominating set of $G$ and, for each vertex $u \not\in S$, there is a vertex $v \in S$ such that $uv$ is an edge and $(S \setminus \{v\}) \cup \{u\}$ is also a dominating set of $G$. The secure domination number of $G$, denoted by $γ_{s}(G)$, is the cardinality of a smallest secure dominating sets of $G$. In this…
▽ More
A subset $S$ of vertices in a graph $G$ is a secure dominating set of $G$ if $S$ is a dominating set of $G$ and, for each vertex $u \not\in S$, there is a vertex $v \in S$ such that $uv$ is an edge and $(S \setminus \{v\}) \cup \{u\}$ is also a dominating set of $G$. The secure domination number of $G$, denoted by $γ_{s}(G)$, is the cardinality of a smallest secure dominating sets of $G$. In this paper, we prove that for any outerplanar graph with $n \geq 4$ vertices, $γ_{s}(G) \geq (n+4)/5$ and the bound is tight.
△ Less
Submitted 12 March, 2024; v1 submitted 11 March, 2024;
originally announced March 2024.
-
Secure Total Domination Number in Maximal Outerplanar Graphs
Authors:
Yasufumi Aita,
Toru Araki
Abstract:
A subset $S$ of vertices in a graph $G$ is a secure total dominating set of $G$ if $S$ is a total dominating set of $G$ and, for each vertex $u \not\in S$, there is a vertex $v \in S$ such that $uv$ is an edge and $(S \setminus \{v\}) \cup \{u\}$ is also a total dominating set of $G$. We show that if $G$ is a maximal outerplanar graph of order $n$, then $G$ has a total secure dominating set of siz…
▽ More
A subset $S$ of vertices in a graph $G$ is a secure total dominating set of $G$ if $S$ is a total dominating set of $G$ and, for each vertex $u \not\in S$, there is a vertex $v \in S$ such that $uv$ is an edge and $(S \setminus \{v\}) \cup \{u\}$ is also a total dominating set of $G$. We show that if $G$ is a maximal outerplanar graph of order $n$, then $G$ has a total secure dominating set of size at most $\lfloor 2n/3 \rfloor$. Moreover, if an outerplanar graph $G$ of order $n$, then each secure total dominating set has at least $\lceil (n+2)/3 \rceil$ vertices. We show that these bounds are best possible.
△ Less
Submitted 8 April, 2024; v1 submitted 5 March, 2024;
originally announced March 2024.
-
IC-SECURE: Intelligent System for Assisting Security Experts in Generating Playbooks for Automated Incident Response
Authors:
Ryuta Kremer,
Prasanna N. Wudali,
Satoru Momiyama,
Toshinori Araki,
Jun Furukawa,
Yuval Elovici,
Asaf Shabtai
Abstract:
Security orchestration, automation, and response (SOAR) systems ingest alerts from security information and event management (SIEM) system, and then trigger relevant playbooks that automate and orchestrate the execution of a sequence of security activities. SOAR systems have two major limitations: (i) security analysts need to define, create and change playbooks manually, and (ii) the choice betwe…
▽ More
Security orchestration, automation, and response (SOAR) systems ingest alerts from security information and event management (SIEM) system, and then trigger relevant playbooks that automate and orchestrate the execution of a sequence of security activities. SOAR systems have two major limitations: (i) security analysts need to define, create and change playbooks manually, and (ii) the choice between multiple playbooks that could be triggered is based on rules defined by security analysts. To address these limitations, recent studies in the field of artificial intelligence for cybersecurity suggested the task of interactive playbook creation. In this paper, we propose IC-SECURE, an interactive playbook creation solution based on a novel deep learning-based approach that provides recommendations to security analysts during the playbook creation process. IC-SECURE captures the context in the form of alert data and current status of incomplete playbook, required to make reasonable recommendation for next module that should be included in the new playbook being created. We created three evaluation datasets, each of which involved a combination of a set of alert rules and a set of playbooks from a SOAR platform. We evaluated IC-SECURE under various settings, and compared our results with two state-of-the-art recommender system methods. In our evaluation IC-SECURE demonstrated superior performance compared to other methods by consistently recommending the correct security module, achieving precision@1 > 0.8 and recall@3 > 0.92
△ Less
Submitted 7 November, 2023;
originally announced November 2023.
-
Simultaneous Adversarial Attacks On Multiple Face Recognition System Components
Authors:
Inderjeet Singh,
Kazuya Kakizaki,
Toshinori Araki
Abstract:
In this work, we investigate the potential threat of adversarial examples to the security of face recognition systems. Although previous research has explored the adversarial risk to individual components of FRSs, our study presents an initial exploration of an adversary simultaneously fooling multiple components: the face detector and feature extractor in an FRS pipeline. We propose three multi-o…
▽ More
In this work, we investigate the potential threat of adversarial examples to the security of face recognition systems. Although previous research has explored the adversarial risk to individual components of FRSs, our study presents an initial exploration of an adversary simultaneously fooling multiple components: the face detector and feature extractor in an FRS pipeline. We propose three multi-objective attacks on FRSs and demonstrate their effectiveness through a preliminary experimental analysis on a target system. Our attacks achieved up to 100% Attack Success Rates against both the face detector and feature extractor and were able to manipulate the face detection probability by up to 50% depending on the adversarial objective. This research identifies and examines novel attack vectors against FRSs and suggests possible ways to augment the robustness by leveraging the attack vector's knowledge during training of an FRS's components.
△ Less
Submitted 11 April, 2023;
originally announced April 2023.
-
Advancing Deep Metric Learning Through Multiple Batch Norms And Multi-Targeted Adversarial Examples
Authors:
Inderjeet Singh,
Kazuya Kakizaki,
Toshinori Araki
Abstract:
Deep Metric Learning (DML) is a prominent field in machine learning with extensive practical applications that concentrate on learning visual similarities. It is known that inputs such as Adversarial Examples (AXs), which follow a distribution different from that of clean data, result in false predictions from DML systems. This paper proposes MDProp, a framework to simultaneously improve the perfo…
▽ More
Deep Metric Learning (DML) is a prominent field in machine learning with extensive practical applications that concentrate on learning visual similarities. It is known that inputs such as Adversarial Examples (AXs), which follow a distribution different from that of clean data, result in false predictions from DML systems. This paper proposes MDProp, a framework to simultaneously improve the performance of DML models on clean data and inputs following multiple distributions. MDProp utilizes multi-distribution data through an AX generation process while leveraging disentangled learning through multiple batch normalization layers during the training of a DML model. MDProp is the first to generate feature space multi-targeted AXs to perform targeted regularization on the training model's denser embedding space regions, resulting in improved embedding space densities contributing to the improved generalization in the trained models. From a comprehensive experimental analysis, we show that MDProp results in up to 2.95% increased clean data Recall@1 scores and up to 2.12 times increased robustness against different input distributions compared to the conventional methods.
△ Less
Submitted 6 December, 2022; v1 submitted 29 November, 2022;
originally announced November 2022.
-
Latent SHAP: Toward Practical Human-Interpretable Explanations
Authors:
Ron Bitton,
Alon Malach,
Amiel Meiseles,
Satoru Momiyama,
Toshinori Araki,
Jun Furukawa,
Yuval Elovici,
Asaf Shabtai
Abstract:
Model agnostic feature attribution algorithms (such as SHAP and LIME) are ubiquitous techniques for explaining the decisions of complex classification models, such as deep neural networks. However, since complex classification models produce superior performance when trained on low-level (or encoded) features, in many cases, the explanations generated by these algorithms are neither interpretable…
▽ More
Model agnostic feature attribution algorithms (such as SHAP and LIME) are ubiquitous techniques for explaining the decisions of complex classification models, such as deep neural networks. However, since complex classification models produce superior performance when trained on low-level (or encoded) features, in many cases, the explanations generated by these algorithms are neither interpretable nor usable by humans. Methods proposed in recent studies that support the generation of human-interpretable explanations are impractical, because they require a fully invertible transformation function that maps the model's input features to the human-interpretable features. In this work, we introduce Latent SHAP, a black-box feature attribution framework that provides human-interpretable explanations, without the requirement for a fully invertible transformation function. We demonstrate Latent SHAP's effectiveness using (1) a controlled experiment where invertible transformation functions are available, which enables robust quantitative evaluation of our method, and (2) celebrity attractiveness classification (using the CelebA dataset) where invertible transformation functions are not available, which enables thorough qualitative evaluation of our method.
△ Less
Submitted 27 November, 2022;
originally announced November 2022.
-
Powerful Physical Adversarial Examples Against Practical Face Recognition Systems
Authors:
Inderjeet Singh,
Toshinori Araki,
Kazuya Kakizaki
Abstract:
It is well-known that the most existing machine learning (ML)-based safety-critical applications are vulnerable to carefully crafted input instances called adversarial examples (AXs). An adversary can conveniently attack these target systems from digital as well as physical worlds. This paper aims to the generation of robust physical AXs against face recognition systems. We present a novel smoothn…
▽ More
It is well-known that the most existing machine learning (ML)-based safety-critical applications are vulnerable to carefully crafted input instances called adversarial examples (AXs). An adversary can conveniently attack these target systems from digital as well as physical worlds. This paper aims to the generation of robust physical AXs against face recognition systems. We present a novel smoothness loss function and a patch-noise combo attack for realizing powerful physical AXs. The smoothness loss interjects the concept of delayed constraints during the attack generation process, thereby causing better handling of optimization complexity and smoother AXs for the physical domain. The patch-noise combo attack combines patch noise and imperceptibly small noises from different distributions to generate powerful registration-based physical AXs. An extensive experimental analysis found that our smoothness loss results in robust and more transferable digital and physical AXs than the conventional techniques. Notably, our smoothness loss results in a 1.17 and 1.97 times better mean attack success rate (ASR) in physical white-box and black-box attacks, respectively. Our patch-noise combo attack furthers the performance gains and results in 2.39 and 4.74 times higher mean ASR than conventional technique in physical world white-box and black-box attacks, respectively.
△ Less
Submitted 23 March, 2022;
originally announced March 2022.
-
Universal Adversarial Spoofing Attacks against Face Recognition
Authors:
Takuma Amada,
Seng Pei Liew,
Kazuya Kakizaki,
Toshinori Araki
Abstract:
We assess the vulnerabilities of deep face recognition systems for images that falsify/spoof multiple identities simultaneously. We demonstrate that, by manipulating the deep feature representation extracted from a face image via imperceptibly small perturbations added at the pixel level using our proposed Universal Adversarial Spoofing Examples (UAXs), one can fool a face verification system into…
▽ More
We assess the vulnerabilities of deep face recognition systems for images that falsify/spoof multiple identities simultaneously. We demonstrate that, by manipulating the deep feature representation extracted from a face image via imperceptibly small perturbations added at the pixel level using our proposed Universal Adversarial Spoofing Examples (UAXs), one can fool a face verification system into recognizing that the face image belongs to multiple different identities with a high success rate. One characteristic of the UAXs crafted with our method is that they are universal (identity-agnostic); they are successful even against identities not known in advance. For a certain deep neural network, we show that we are able to spoof almost all tested identities (99\%), including those not known beforehand (not included in training). Our results indicate that a multiple-identity attack is a real threat and should be taken into account when deploying face recognition systems.
△ Less
Submitted 1 October, 2021;
originally announced October 2021.
-
On Brightness Agnostic Adversarial Examples Against Face Recognition Systems
Authors:
Inderjeet Singh,
Satoru Momiyama,
Kazuya Kakizaki,
Toshinori Araki
Abstract:
This paper introduces a novel adversarial example generation method against face recognition systems (FRSs). An adversarial example (AX) is an image with deliberately crafted noise to cause incorrect predictions by a target system. The AXs generated from our method remain robust under real-world brightness changes. Our method performs non-linear brightness transformations while leveraging the conc…
▽ More
This paper introduces a novel adversarial example generation method against face recognition systems (FRSs). An adversarial example (AX) is an image with deliberately crafted noise to cause incorrect predictions by a target system. The AXs generated from our method remain robust under real-world brightness changes. Our method performs non-linear brightness transformations while leveraging the concept of curriculum learning during the attack generation procedure. We demonstrate that our method outperforms conventional techniques from comprehensive experimental investigations in the digital and physical world. Furthermore, this method enables practical risk assessment of FRSs against brightness agnostic AXs.
△ Less
Submitted 29 September, 2021;
originally announced September 2021.
-
Maximum Number of Steps of Topswops on 18 and 19 Cards
Authors:
Kento Kimura,
Atsuki Takahashi,
Tetsuya Araki,
Kazuyuki Amano
Abstract:
Let $f(n)$ be the maximum number of steps of Topswops on $n$ cards. In this note, we report our computational experiments to determine the values of $f(18)$ and $f(19)$. By applying an algorithm developed by Knuth in a parallel fashion, we conclude that $f(18)=191$ and $f(19)=221$.
Let $f(n)$ be the maximum number of steps of Topswops on $n$ cards. In this note, we report our computational experiments to determine the values of $f(18)$ and $f(19)$. By applying an algorithm developed by Knuth in a parallel fashion, we conclude that $f(18)=191$ and $f(19)=221$.
△ Less
Submitted 15 March, 2021;
originally announced March 2021.
-
Rank Position Forecasting in Car Racing
Authors:
Bo Peng,
Jiayu Li,
Selahattin Akkas,
Fugang Wang,
Takuya Araki,
Ohno Yoshiyuki,
Judy Qiu
Abstract:
Forecasting is challenging since uncertainty resulted from exogenous factors exists. This work investigates the rank position forecasting problem in car racing, which predicts the rank positions at the future laps for cars. Among the many factors that bring changes to the rank positions, pit stops are critical but irregular and rare. We found existing methods, including statistical models, machine…
▽ More
Forecasting is challenging since uncertainty resulted from exogenous factors exists. This work investigates the rank position forecasting problem in car racing, which predicts the rank positions at the future laps for cars. Among the many factors that bring changes to the rank positions, pit stops are critical but irregular and rare. We found existing methods, including statistical models, machine learning regression models, and state-of-the-art deep forecasting model based on encoder-decoder architecture, all have limitations in the forecasting. By elaborative analysis of pit stops events, we propose a deep model, RankNet, with the cause effects decomposition that modeling the rank position sequence and pit stop events separately. It also incorporates probabilistic forecasting to model the uncertainty inside each sub-model. Through extensive experiments, RankNet demonstrates a strong performance improvement over the baselines, e.g., MAE improves more than 10% consistently, and is also more stable when adapting to unseen new data. Details of model optimization, performance profiling are presented. It is promising to provide useful forecasting tools for the car racing analysis and shine a light on solutions to similar challenging issues in general forecasting problems.
△ Less
Submitted 23 October, 2020; v1 submitted 4 October, 2020;
originally announced October 2020.
-
A tight analysis of Kierstead-Trotter algorithm for online unit interval coloring
Authors:
Tetsuya Araki,
Koji M. Kobayashi
Abstract:
Kierstead and Trotter (Congressus Numerantium 33, 1981) proved that their algorithm is an optimal online algorithm for the online interval coloring problem. In this paper, for online unit interval coloring, we show that the number of colors used by the Kierstead-Trotter algorithm is at most $3 ω(G) - 3$, where $ω(G)$ is the size of the maximum clique in a given graph $G$, and it is the best possib…
▽ More
Kierstead and Trotter (Congressus Numerantium 33, 1981) proved that their algorithm is an optimal online algorithm for the online interval coloring problem. In this paper, for online unit interval coloring, we show that the number of colors used by the Kierstead-Trotter algorithm is at most $3 ω(G) - 3$, where $ω(G)$ is the size of the maximum clique in a given graph $G$, and it is the best possible.
△ Less
Submitted 28 September, 2016;
originally announced September 2016.
-
On the distance preserving trees in graphs
Authors:
Toru Araki,
Shingo Osawa,
Takashi Shimizu
Abstract:
For a vertex $v$ of a graph $G$, a spanning tree $T$ of $G$ is distance-preserving from $v$ if, for any vertex $w$, the distance from $v$ to $w$ on $T$ is the same as the distance from $v$ to $w$ on $G$. If two vertices $u$ and $v$ are distinct, then two distance-preserving spanning trees $T_{u}$ from $u$ and $T_{v}$ from $v$ are distinct in general. A purpose of this paper is to give a characteri…
▽ More
For a vertex $v$ of a graph $G$, a spanning tree $T$ of $G$ is distance-preserving from $v$ if, for any vertex $w$, the distance from $v$ to $w$ on $T$ is the same as the distance from $v$ to $w$ on $G$. If two vertices $u$ and $v$ are distinct, then two distance-preserving spanning trees $T_{u}$ from $u$ and $T_{v}$ from $v$ are distinct in general. A purpose of this paper is to give a characterization for a given weighted graph $G$ to have a spanning tree $T$ such that $T$ is a distance-preserving spanning tree from distinct two vertices.
△ Less
Submitted 23 July, 2014;
originally announced July 2014.
