In the context of the Classification and Regression Trees (CART) algorithm, the efficient splitting of categorical features using standard criteria like GINI and Entropy is well-established. However, using the Mean Absolute Error (MAE) criterion for categorical features has traditionally relied on various numerical encoding methods. This paper demonstrates that unsupervised numerical encoding methods are not viable for MAE criteria. Furthermore, we present a novel and efficient splitting algorithm that addresses the challenges of handling categorical features with the MAE criterion. Our findings underscore the limitations of existing approaches and offer a promising solution to enhance the handling of categorical data in CART algorithms.

Given n piecewise-linear unimodal functions f_1,… ,f_n:ℝ → ℝ and an integer 1 ≤ k ≤ n, the Unimodal-Cost k-Median problem asks for k real numbers y_1,… ,y_k minimizing ∑_{i=1}^n min_{1 ≤ r ≤ k} f_i(y_r). Let m be the number of breakpoints: the total number of affine-piece endpoint occurrences plus one occurrence at a chosen minimizer of each function. We give an exact algorithm running in O((m+nlog n)log m ⋅ min{k, log m√{klog m}, log m⋅ 2^O(√{log k log log m})}) . The first term inside the minimum comes from a direct k-stage dynamic program. The other two use the minimum-weight k-link path algorithms of Aggarwal et al. [Aggarwal et al., 1994] and Schieber [Schieber, 1998] for Monge costs, replacing their O(1) edge-weight access by batched access to the implicit transition costs.

Unauthorized editing of speech recordings poses a significant threat to the security and authenticity of speeches, particularly in the forensic and legal fields. Even worse, the speech is increasingly at risk of being tampered with due to the development of AI techniques (e.g., Audio Deepfake). It is difficult for normal users to guarantee what they say has not been illegally changed. Audio watermark techniques are recognized as an active method against speech forgery. However, such techniques suffer from audio quality degradation and non-real-time insertion. Therefore, they cannot be adopted into real-time voice applications against forgery on remote recordings, e.g., phone calls, live broadcasts, and online meetings. Fortunately, high-definition (HD) audio techniques provide ultrasonic bands without distortion. Therefore, ultrasonic creditable factors can be utilized. We propose an audio tamper-proof system, named Aegis. It provides commodity mobile devices (e.g., smartphones) with an effective method of real-time insertion of inaudible creditable factors. Users can claim that audio with no or mismatched ultrasound is invalid and illegal. In particular, we explore a novel acoustic nonlinear phenomenon where audible signals can be modulated onto the ultrasonic spectrum. By emphasizing the correlation between speech signals and ultrasound, we realize effective defense against various tampering methods. Extensive evaluations demonstrate that Aegis yields a detection accuracy of 99.5% on average even against unseen tampering methods.

Continuous authentication is increasingly critical for cyber security. However, existing approaches are time-consuming due to their simplistic signal modulation and low efficiency in feature extraction. In this paper, we propose a continuous authentication technique, OnePiece. OnePiece is free from the requirement of in-ear microphones, which are necessary for existing earphone authentication systems. It exploits out-ear microphones for biometrics extraction, which are ubiquitous on off-the-shelf earphones. We analyze the acoustic response model of ears towards out-ear microphones via the air, which is different from that towards in-ear microphones. A frequency-varying ultrasonic modulation scheme is proposed to characterize in-depth ear biometrics in user-friendly, error-free, and time-efficient ways. Therefore, OnePiece enables quick-pass authentication once users wear the earphones, followed by continuous authentication covering the whole course. Moreover, we propose a wake-up mechanism to reduce the consumed power, which addresses the key power consumption issue in ultrasonic sensing techniques. Particularly, OnePiece can be smoothly deployed on off-the-shelf wired and wireless earphones. It performs good cross-device performance in which users just register only once. Extensive evaluations are conducted to validate its effectiveness under real-world scenarios.

The Stacker Crane Problem (SCP) is a variant of the Traveling Salesman Problem. In SCP, pairs of pickup and delivery points are designated on a graph, and a crane must visit these points to move objects from each pickup location to its respective delivery point. The goal is to minimize the total distance traveled. SCP is known to be NP-hard, even on trees. The only positive results, in terms of polynomial-time solvability, apply to graphs that are topologically equivalent to a path or a cycle. We propose an algorithm that is optimal for each fixed topology, running in near-linear time. This is achieved by demonstrating that the problem is fixed-parameter tractable (FPT) when parameterized by both the cycle rank and the number of branch vertices.

For safety guard and crime prevention, video surveillance systems have been pervasively deployed in many security-critical scenarios, such as the residence, retail stores, and banks. However, these systems could be infiltrated by the adversary and the video streams would be modified or replaced, i.e., under the video forgery attack. The prevalence of Internet of Things (IoT) devices and the emergence of Deepfake-like techniques severely emphasize the vulnerability of video surveillance systems under such attacks. To secure existing surveillance systems, in this paper we propose a vision-WiFi cross-modal video forgery detection system, namelyWiSil. Leveraging a theoretical model based on the principle of signal propagation,WiSilconstructs wave front information of the object in the monitoring area from WiFi signals. With a well-designed deep learning network,WiSilfurther recovers silhouettes from the wave front information. Based on a Siamese network-based semantic feature extractor,WiSilcan eventually determine whether a frame is manipulated by comparing the semantic feature vectors extracted from the video’s silhouette with those extracted from the WiFi’s silhouette. We enhance the basic version ofWiSilFang et al. 2023 by developing a model compression method and a forgery trace localization method. Extensive experiments show thatWiSilachieves 95%$+$accuracy in detecting tampered frames.

With a wide range of common and privacy-sensitive applications, smartphones are frequently accessed for substantial personal information. Therefore, user-friendliness and security are crucial for user authentication on smartphones. Recently, convenient and secure biometric-based authentication is widely employed for smartphones, where the facial authentication stands out due to its potential for advancements in both user-friendliness and security. However, existing facial authentication methods possess some defects. For example, camera-based methods require good illumination conditions and are susceptible to 2D spoofing attacks. Moreover, previous acoustic-based methods either require camera assistance, or still suffer from 3D spoofing attacks. Even worse, some acoustic-based methods use audible sound waves, causing discomfort to users. To solve these questions, in this paper we propose UltraFace, an anti-spoofing and user-friendly facial authentication system on smartphones. It extracts facial geometry features and acoustic impedance features from imperceptible ultrasound. Leveraging the principle of ultrasound propagation, UltraFace correlates spectrograms of reflected signals with facial biometrics. Utilizing a deep learning model as a feature extractor, UltraFace mines fine-grained facial geometry features and acoustic impedance features from the spectrograms for accurate user authentication. Extensive experiments show that UltraFace achieves $97.2 \%$ accuracy in user authentication and can effectively defend against spoofing attacks. Furthermore, UltraFace exhibits robustness for long-term usage.

Smartwatches have become increasingly prevalent in people’s daily lives, offering support for a wide range of privacy and security-sensitive applications, such as SMS messaging and mobile payment. Consequently, there is an imperative need for independent user authentication on smartwatches to safeguard against property loss and personal privacy breaches. However, current authentication methods rely on passwords, leaving users vulnerable to shoulder surfing attacks. Moreover, existing biometric-based authentication methods either require dedicated sensors or cannot support continuous authentication. In this paper, we propose a replay-resistant continuous authentication system on smartwatches, namely WristPass. It extracts acoustic impedance biometrics from ultrasonic signals. Leveraging a theoretical model based on the principle of ultrasound propagation, WristPass correlates spectrograms of reflected signals with impedance features of wrist skin. Utilizing a deep learning model as a feature extractor, WristPass mines fine-grained impedance features from the spectrograms for accurate user authentication. Additionally, to prevent WristPass from replay attacks, we design a device fingerprinting method to detect replayed signals. Extensive experiments show that WristPass can achieve 96.7% accuracy in user authentication. Furthermore, WristPass exhibits robustness for long-term usage.

Continuous authentication is increasingly critical for cyber security. However, existing approaches are time-inefficient due to their simple signal modulation with low-effective feature extraction throughput. In this paper, we propose a continuous authentication technique, OnePiece. OnePiece is free from the requirement of in-ear microphones, which are necessary for existing earphone authentication systems. It exploits out-ear microphones for biometrics extraction, which are ubiquitous on off-the-shelf earphones. We analyze the acoustic response model of ears towards out-ear microphones via the air, which is different from that towards in-ear microphones. A frequency-varying ultrasonic modulation scheme is proposed to characterize in-depth ear biometrics in user-friendly, error-free, and time-efficient ways. Therefore, OnePiece enables quick-pass authentication once users wear the earphones, followed by continuous authentication covering the whole course. Moreover, we propose a wake-up mechanism to reduce the consumed power, which addresses the key power consumption issue in ultrasonic sensing techniques. Particularly, OnePiece can be smoothly deployed on off-the-shelf wired and wireless earphones. It performs good cross-device performance in which users just register only once. Extensive evaluations are conducted to validate its effectiveness under real-world scenarios.

Covert eavesdropping via microphones has always been a major threat to user privacy. Benefiting from the acoustic non-linearity property, the ultrasonic microphone jammer (UMJ) is effective in resisting this long-standing attack. However, prior UMJ researches underestimate adversary's attacking capability in reality and miss critical metrics for a thorough evaluation. The strong assumptions of adversary unable to retrieve information under low word recognition rate, and adversary's weak denoising abilities in the threat model make these works overlook the vulnerability of existing UMJs. As a result, their UMJs' resilience is overestimated. In this paper, we refine the adversary model and completely investigate potential eavesdropping threats. Correspondingly, we define a total of 12 metrics that are necessary for evaluating UMJs' resilience. Using these metrics, we propose a comprehensive framework to quantify UMJs' practical resilience. It fully covers three perspectives that prior works ignored to some degree, i.e., ambient information, semantic comprehension, and collaborative recognition. Guided by this framework, we can thoroughly and quantitatively evaluate the resilience of existing UMJs towards eavesdroppers. Our extensive assessment results reveal that most existing UMJs are vulnerable to sophisticated adverse approaches. We further outline the key factors influencing jammers' performance and present constructive suggestions for UMJs' future designs.

Ultrasonic microphone jammers protect speech privacy from being eavesdropped by leveraging microphones' non-linearity. However, existing jammers merely introduce independent noises and are vulnerable to capable adversaries who adopt advanced denoising techniques. We propose a novel jammer, namely MicFrozen. It reduces the signal-to-noise ratio (SNR) at the adversary's microphone from two perspectives, i.e., cancelling speech signals and adding noises that are difficult to be removed. It effectively cancels out the protected speech signals at the adversary without compromising the delivery of the signal to the targeted individual. MicFrozen further adds coherent noises that are coupled with the speech signals to resist removal by the adversary. Extensive evaluations show that MicFrozen can cause a low SNR (-13.6 dB) at the adversary and up to 96.9% of speech signals are unrecognized at the adversary even if state-of-the-art denoising techniques are adopted by the adversary. Comprehensive experiments demonstrate the effectiveness of MicFrozen confronted by capable adversaries.

Eavesdropping via inertial measurement units (IMUs) has brought growing concerns over smartphone users’ privacy. In such attacks, adversaries utilize IMUs, including accelerometers and gyroscopes, which require zero permissions for access to acquire speeches. A common countermeasure is to limit sampling rates (within 200 Hz) to reduce overlap of vocal fundamental bands (85$\sim$255 Hz) and inertial measurements (0$\sim$100 Hz). Nevertheless, we observe that IMUs sampling below 200 Hz still record adequate speech-related information because of aliasing distortions. Accordingly, we propose a practical side-channel attack, namelyInertiEAR, to break the defense of sampling rate restriction on the zero-permission eavesdropping. It leverages accelerometers and gyroscopes jointly to eavesdrop on both top and bottom speakers in smartphones. We exploit coherence between responses of the built-in accelerometer and gyroscope using a mathematical model. The coherence allows precise segmentation without manual assistance. We also mitigate the impact of hardware diversity and achieve better device-independent performance than existing approaches that have to massively increase training data from different smartphones for a scalable network model. These two advantages re-enable zero-permission attacks but also extend the attacking surface and endangering degree to off-the-shelf smartphones.InertiEARachieves the recognition accuracy of 78.8% with the cross-device accuracy of up to 60.9% among 12 smartphones.

Covert eavesdropping via microphones has always been a major threat to user privacy. Benefiting from the acoustic non-linearity property, the ultrasonic microphone jammer (UMJ) is effective in resisting this long-standing attack. However, prior UMJ researches underestimate adversary’s attacking capability in reality and miss critical metrics for a thorough evaluation. The strong assumptions of adversary unable to retrieve information under low word recognition rate, and adversary’s weak denoising abilities in the threat model make these works overlook the vulnerability of existing UMJs. As a result, their UMJs’ resilience is overestimated. In this paper, we refine the adversary model and completely investigate potential eavesdropping threats. Correspondingly, we define a total of 12 metrics that are necessary for evaluating UMJs’ resilience. Using these metrics, we propose a comprehensive framework to quantify UMJs’ practical resilience. It fully covers three perspectives that prior works ignored in some degree, i.e., ambient information, semantic comprehension, and collaborative recognition. Guided by this framework, we can thoroughly and quantitatively evaluate the resilience of existing UMJs towards eavesdroppers. Our extensive assessment results reveal that most existing UMJs are vulnerable to sophisticated adverse approaches. We further outline the key factors influencing jammers’ performance and present constructive suggestions for UMJs’ future designs.

IMU-based eavesdropping has brought growing concerns over smartphone users’ privacy. In such attacks, adversaries utilize IMUs that require zero permissions for access to acquire speeches. A common countermeasure is to limit sampling rates (within 200 Hz) to reduce overlap of vocal fundamental bands (85-255 Hz) and inertial measurements (0-100 Hz). Nevertheless, we experimentally observe that IMUs sampling below 200 Hz still record adequate speech-related information because of aliasing distortions. Accordingly, we propose a practical side-channel attack, InertiEAR, to break the defense of sampling rate restriction on the zero-permission eavesdropping. It leverages IMUs to eavesdrop on both top and bottom speakers in smartphones. In the InertiEAR design, we exploit coherence between responses of the built-in accelerometer and gyroscope and their hardware diversity using a mathematical model. The coherence allows precise segmentation without manual assistance. We also mitigate the impact of hardware diversity and achieve better device-independent performance than existing approaches that have to massively increase training data from different smartphones for a scalable network model. These two advantages re-enable zero-permission attacks but also extend the attacking surface and endangering degree to off-the-shelf smartphones. InertiEAR achieves a recognition accuracy of 78.8% with a cross-device accuracy of up to 49.8% among 12 smartphones.