Piggyback: Designing an Invisible Payload Carrier via Greedy Heuristics and Knapsack Optimization

Author: Md. Rakibul Hasan (@rxxeron)
Academic Affiliation: B.Sc. in Information and Communications Engineering (ICE), Dept. of Computer Science and Engineering, East West University
Course: ICE245 — Algorithm Design (Lab 4 & Lab 13 Mini Project)
Core Concepts: Telecommunications Piggybacking, Greedy Heuristic Allocation, 0/1 Knapsack Optimization, Signal Steganography

1. Academic Premise: Translating Network Piggybacking into Algorithm Design

In telecommunication protocol design (e.g. Sliding Window ARQ, TCP ACK piggybacking), piggybacking is the technique of attaching acknowledgment headers or secondary payloads onto outgoing data packets rather than transmitting dedicated control frames. This conserves channel bandwidth and minimizes protocol overhead.

In ICE245: Algorithm Design, I formulated a novel project extending this telecommunication principle to information hiding:

• How can high-entropy binary payloads (authentication tokens, encrypted metadata, telemetry) be "piggybacked" invisibly onto existing communication carriers (digital images, multimedia streams)?
• How can we prove mathematically that the carrier distortion remains below the threshold of human and statistical detectability?

Rather than naive sequential Least Significant Bit (LSB) embedding—which produces easily detectable statistical distortions (Chi-Square attacks)—I designed Piggyback: an interactive algorithm workbench combining Greedy Minimization Heuristics and Dynamic Programming Knapsack Allocation.

text
+--------------------------------------------------------------------------------------------------+
|                                PIGGYBACK ALGORITHM WORKBENCH                                     |
+--------------------------------------------------------------------------------------------------+
|                                                                                                  |
|   [RAW PAYLOAD INGESTION]                                                                        |
|   ├── Binary Bitstream Serialization & Shannon Entropy Calculation                               |
|   └── Dynamic Chunk Partitioning into Variable-Length Bit-Planes                                 |
|              │                                                                                   |
|              ▼                                                                                   |
|   [GREEDY CARRIER ALLOCATION ENGINE (ICE245 LAB 4)]                                              |
|   ├── Spatial 3x3 Neighborhood Variance Scanning (Local Variance Gradient Calculation)          |
|   ├── Priority Queue Ranking of Carrier Channels by Visual Entropy Tolerance                     |
|   └── Greedy Assignment: High-Entropy Edges absorb 3 LSBs; Smooth Planes absorb 0-1 LSBs         |
|              │                                                                                   |
|              ▼                                                                                   |
|   [0/1 KNAPSACK OPTIMIZATION ENGINE (ICE245 LAB 13)]                                             |
|   ├── Value Function: Total Payload Bits Embedded (Maximization)                                 |
|   ├── Weight Function: Mean Squared Error (MSE) Distortion Incurred                              |
|   └── Capacity Constraint: Total Distortion <= Peak Signal-to-Noise Ratio (PSNR > 42 dB)         |
|              │                                                                                   |
|              ▼                                                                                   |
|   [VECTORIZED RECONSTRUCTION & PYQT6 GUI]                                                        |
|   ├── NumPy C-Extension Accelerated Bitwise Masking (& 0xFE, | bit)                              |
|   └── Decoupled Multithreaded GUI (Worker Thread Architecture preventing UI Freezing)             |
|                                                                                                  |
+--------------------------------------------------------------------------------------------------+

2. Algorithmic Breakdown & Mathematical Formulations

A. Greedy Payload Distribution (Lab 4 Foundation)

Standard steganography embeds bits sequentially across pixels $(0,0), (0,1), (0,2)...$, creating contiguous zones of modified variance.

The Piggyback greedy algorithm sorts carrier pixels based on their Local Spatial Variance Gradient $\sigma^2$:

• Smooth Regions (Low Variance): The Human Visual System (HVS) is highly sensitive to color shifts in flat backgrounds. The greedy allocator restricts embedding here to 0 or at most 1 LSB.
• Textured Regions & Edge Gradients (High Variance): Sharp image contours naturally mask noise. The greedy allocator assigns 2 to 3 LSBs to these high-entropy channels.

python
def calculate_spatial_variance(image_matrix: np.ndarray) -> np.ndarray:
    """Calculates local 3x3 spatial gradient variance across the carrier matrix."""
    kernel_size = 3
    mean = cv2.blur(image_matrix.astype(np.float64), (kernel_size, kernel_size))
    sq_mean = cv2.blur(image_matrix.astype(np.float64)**2, (kernel_size, kernel_size))
    variance = sq_mean - (mean ** 2)
    return variance

B. 0/1 Knapsack Optimization for Capacity Slicing (Lab 13)

When payload streams exceed the capacity of high-variance regions, how do we decide which payload chunks to embed without degrading the signal below acceptable broadcast standards?

I formulated this as a Bounded 0/1 Knapsack Problem:

• Let each candidate pixel cluster $i$ be an item.
• Value $v_i$: Number of payload bits embedded in cluster $i$.
• Weight $w_i$: Mathematical Mean Squared Error (MSE) introduced into the carrier channel.
• Knapsack Capacity $W$: The strict upper bound on allowable distortion ensuring Peak Signal-to-Noise Ratio (PSNR) stays above broadcast quality thresholds ($> 42\text{ dB}$).

$$\text{Maximize } \sum_{i=1}^{n} v_i x_i \quad \text{subject to} \quad \sum_{i=1}^{n} w_i x_i \le W_{\text{max MSE}}, \quad x_i \in {0, 1}$$

3. High-Performance Vectorization & UI Architecture

• NumPy Matrix Acceleration: Python for loops over large images ($1024 \times 1024 \times 3 = 3,145,728$ bytes) execute in ~2.8 seconds. By refactoring bit masking into vectorized NumPy operations, embedding time dropped to under 110ms (a 25x speedup).
• PyQt6 Worker Thread Separation: Heavy image matrix convolutions run inside a background QThread. Progress signals update a real-time PSNR dial on the PyQt6 interface without causing frame drops or UI stuttering.

4. Experimental Results & Verification

• Signal Quality (PSNR): Maintained an average PSNR of 44.8 dB across standard benchmark images (Lena, Mandrill, Peppers), well above the standard 38 dB threshold of visual detectability.
• Payload Recovery: 100.0% lossless bit extraction verified via automated SHA-256 payload checksum validation.
• Histogram Uniformity: Preserved first-order pixel histogram distributions, defeating automated Chi-Square visual steganalysis attacks.