#  ObNoCs: Protecting Network-on-Chip Fabrics Against Reverse-Engineering
Attacks

Dipal Halder<EMAIL_ADDRESS>https://orcid.org/0000-0003-2593-0493
University of FloridaGainesvilleFLUSA32611 ,  Maneesh Merugu
<EMAIL_ADDRESS>https://orcid.org/0000-0002-0124-8839 University of
FloridaGainesvilleFLUSA32611 and  Sandip Ray<EMAIL_ADDRESS>https://orcid.org/0000-0002-8671-5052 University of
FloridaGainesvilleFLUSA32611

###### Abstract.

Modern System-on-Chip designs typically use Network-on-Chip (NoC) fabrics to
implement coordination among integrated hardware blocks. An important class of
security vulnerabilities involves a rogue foundry reverse-engineering the NoC
topology and routing logic. In this paper, we develop an infrastructure,
ObNoCs, for protecting NoC fabrics against such attacks. ObNoCs systematically
replaces router connections with switches that can be programmed after
fabrication to induce the desired topology. Our approach provides provable
redaction of NoC functionality: switch configurations induce a large number of
legal topologies, only one of which corresponds to the intended topology. We
implement the ObNoCs methodology on Intel Quartus™ Platform, and experimental
results on realistic SoC designs show that the architecture incurs minimal
overhead in power, resource utilization, and system latency.

Hardware security, Obfuscation, Supply-chain attacks, Communication fabrics

This paper has been accepted for publication in CASES 2023

††copyright: none††ccs: Security and privacy Hardware reverse engineering

##  1\. Introduction

System-on-Chip (SoC) designs are architected by integration of predesigned
hardware blocks, — referred to as “Intellectual Properties” or “IPs”, — which
communicate through a variety of Network-on-Chip (NoC) fabrics to realize the
system functionality. The NoC fabrics realize on-chip communication using a
collection of routers connected to form a topology optimized for the workload
of the targeted SoC. The NoC fabrics have the advantage of being more scalable
and power-efficient than traditional bus-based communications and have
proliferated significantly in recent years as central coordination vehicles in
SoC designs.

A sensitive security asset in NoC-based designs is the topology of the NoC
itself. Reverse-engineering the NoC topology enables a rogue entity to infer a
variety of system-level parameters of the SoC, including the targeted latency
for a variety of inter-IP communications on different workloads, sensitivity
of communication at different life cycles, etc. On the other hand, SoCs today
are designed and fabricated through a complex, globally distributed supply
chain, which includes foundries, packaging, assembly, testing facilities, etc.
A rogue player in this supply chain can perform reverse-engineering attacks,
i.e., reconstruct the NoC topology and parameters (see Section 2.3). The
reverse-engineering can target a layout-level design of the SoC (in case of a
foundry) or a fabricated wafer or chip (in case of assembly, packaging, and
testing facility). It is crucial to protect such develop techniques to protect
NoC topologies from reverse-engineering in such untrusted facilities.

In this paper, we address this security problem through a novel obfuscation
technology to conceal the topology of NoC interconnects in SoC designs. Given
an NoC interconnect, our framework ObNoCs enables systematic transformation of
router ports in the interconnect with programmable switches. The switches can
be configured to realize a variety of topologies after fabrication by
programming a specific set of state elements, only one of which corresponds to
the original topology of the fabric. We refer to the switch configuration
corresponding to the original topology as the activation package. We show how
to implement this approach with low overhead using a collection of
multiplexers controlled by programmable registers. The ObNoCs methodology has
been implemented on top of Intel™ Quartus™ platform (qprime, ), and our
experiments on realistic SoC designs show that the overhead of ObNoCs in power
or resource utilization is minimal.

In this section, we first provide a toy motivational example to illustrate the
key idea of ObNoCs. We then discuss the contributions of the paper in greater
detail.

###  1.1. Motivational Example

|
---|---
(a) | (b)
Figure 1. NoC Interconnect Transformation Topology Obfuscation. (a) An NoC-
based SoC Design Example with a simple Tree Topology. (b) Transformation of
the outgoing edge of router R1

Figure 2. Example of custom MUX based transformation for outgoing signals of
Router1 to IP6, Router 3, Router 4 ,and Router 5

Consider the SoC design shown in Fig. 1(a). It includes an NoC with five
routers organized in a simple tree network. Suppose we want to redact the
connection $R_{1}\rightarrow\mbox{IP}_{6}$, Fig. 1(b) shows the method to
transform this connection. In particular, $R_{1}$ is connected to the input of
a $1\times 4$ demultiplexer and the output of the demultiplexer is connected
to the four different hardware blocks. We call this circuitry the DEMUX
switch. The control of the DEMUX switch is connected to a register that can be
programmed after fabrication, and the control bits determine which IP is
actually connected to $R_{1}$ in this port. If the register is programmed with
the bits 00 then $R_{1}$ would be connected in this port to $\mbox{IP}_{6}$
which corresponds to the original topology. Note that each pattern of bits
from 00 through 11 corresponds to some connection, e.g., 01 would correspond
to $R_{1}\rightarrow R_{3}$ and 10 to $R_{1}\rightarrow R_{4}$.

Fig. 2 shows how the transformation above would be implemented for router
$R_{1}$. In particular, we exercise $4\times 1$ MUX to achieve a _MUX-DEMUX_
based switch for each port of the router that we need to redact. This makes
the architecture of ObNoCs 2-stage where the first stage acts as the DEMUX
switch and the second stage as the MUX switch. The control bits for this _MUX-
DEMUX_ switch are connected to a register which can be programmed at runtime.

From the example, it is clear that the NoC obfuscated by ObNoCs would have the
same topological behavior as the unobfuscated NoC if the “right” control bits
are provided. We refer to this bit pattern as activation package. On the other
hand, the assignment of the activation package bits to the register only
happens after the fabricated SoC is returned to the OEM from the foundry; when
the SoC is in an untrusted facility (e.g., foundry, assembly, or test), the
activation package is not available. Furthermore, other bit patterns in
addition to the activation package also correspond to other perfectly viable
NoC topologies; indeed, without access to the activation package, there is no
way to decide which one of the viable topologies was the one actually intended
by the designer. We make this statement formal in Section 4. Correspondingly,
a facility attempting to reverse-engineer the SoC does not have a way to
determine the correct topology (among the viable ones) without access to the
activation package.

###  1.2. Contributions of the Paper

There has been significant recent research on hardware obfuscation. We recount
some of this work in Section 6. A popular approach for hardware obfuscation is
logic locking, where a hardware logic design is extended with a dedicated
locking circuitry such that a correct output is produced only after a special
bit sequence (or “activation package”) has been provided. ObNoCs can be viewed
as a focused locking technique specifically targeted for NoC interconnects.
However, there are important differences between traditional logic locking and
ObNoCs. First, logic locking has been generally targeted for IP-level designs.
Since the traditional locking circuitries incur significant overhead, the cost
of applying it to a complete SoC would be prohibitive. Furthermore, logic-
locking techniques have been shown to be vulnerable to a variety of attacks
(paar, ). In contrast, ObNoCs provides provable protection against reverse-
engineering attacks from an adversary without access to the activation
package.

The paper makes the following important contributions.

  * •

To our knowledge, ObNoCs represents the first obfuscation methodology for
system-level interactions of SoC designs.

  * •

ObNoCs realizes transformation of interconnect topology through a novel
switching architecture that systematically redacts connection structures using
programmable MUXs.

  * •

Our methodology provides provable assurance of protection of obfuscated
topologies against reverse-engineering attacks.

  * •

We demonstrate through extensive experimental results that the methodology
incurs minimal overhead in power and resource utilization and minimal impact
on timing and path delay on realistic SoC designs.

The remainder of the paper is organized as follows. Section 2 discusses the
relevant background. Section 3 describes the ObNoCs obfuscation architecture
and Section 4 provides a security analysis. We discuss experimental results in
Section 5. We discuss related work in Section 6 and conclude in Section 7.

##  2\. Background

###  2.1. NoC Fabrics

The primary coordination mechanism for IPs in an SoC is message-based
communication. Consequently, the communication fabrics constitute a crucial
component of an SoC design. Traditional communication fabrics used point-to-
point, crossbar, or bus architectures. More recently, NoC fabrics have gained
popularity in industrial SoCs. An NoC involves a collection of routers
connected to realize a target topology. Many industrial SoC designs make use
of a tree topology, although other networks such as cycle, mesh, or torus are
also in use (baytrail, ). Routers in an NoC typically include configurable
routing tables which can be reconfigured if necessary by the operating system
at boot-time. A key advantage of NoC architecture is the flexibility provided
in implementing power management with low overhead as it is possible to simply
shut off (or reducing high-speed functionality) routers in the sub-network
when message communication through the sub-network is reduced. Note of course
that these benefits do come with a number of challenges, including complex
optimization requirements for achieving power utilization, fault tolerance,
quality of service (QoS), and CAD support for NoC design (re6, ). For
instance, to address the challenge of high throughput performance, Pathania et
al.(re8, )introduced a unique topology-based performance heterogeneity which
exploits many-core heterogeneity to extract more performance. Indeed, our work
also accounts for resource utilization as an overhead metric to trade off for
achieving security goals.

###  2.2. SoC Supply Chain Security

Semiconductor design has evolved over the past decade into a global enterprise
incorporating 3PIP (third-party IP) vendors, IC design houses, fabrication
labs, and testing facilities dispersed over multiple countries and continents.
The globalization in the supply chain has been driven by a number of factors,
including aggressive time-to-market requirements, miniaturization of VLSI
technology, increased fabrication and validation costs, etc. In particular,
the exponential shrinkage of transistor nodes over the past decades has
enabled the IC designers to pack complex, multi-core and many-core designs
with advanced performance in area and power-constrained chip designs, with a
resultant increase in the price of fabrication. As a result, a majority of the
semiconductor companies are going fabless and outsourcing chip fabrication to
globally distributed remote foundries. An unfortunate upshot is that it is
possible for a rogue foundry to mount a variety of attacks subverting the
design and production of the system. One class of attacks involves alteration
of the design by inserting malicious Trojan circuitry. Another class of
attacks includes reverse engineering, possibly targeting the entire SoC or
some of the key IPs. Other supply chain attacks include cloning, piracy,
counterfeiting, recycling, and overproduction.

###  2.3. Reverse-Engineering Attacks

Reverse engineering is the technique of extracting data from a chip by
dissecting its functional elements and constituent parts. In the context of
NoCs, the goal of the reverse-engineering attacks is to extract information of
the NoC topology from an SoC implementation (either as netlist or as a
fabricated silicon). Although there have not been dedicated techniques
specifically targeted to reverse-engineer NoC topologies, this can be
accomplished by common methods such as imaging, side-channel analysis, and
micro probing all of which have been extensively researched. Torrance et al.
have discussed several types of reverse engineering, of which the products are
disassembling, system-level analysis, and circuit extraction in (re0, ). Gomez
et al. described a method that uses image processing to recreate a chip’s gate
netlist after it has been decapped and delayered. Using this method, the whole
netlist is rebuilt by teaching an image processing tool to identify common
cell layout patterns and extract routing information (re9, ). Additionally,
there are purely algorithmic ways to reverse engineering digital circuits for
the purpose of inferring a high-level netlist with components like register
files, adders, and counters from unstructured netlists. For instance,
Subramanyan et al. (re2, ) segmented the netlist into potential/candidate
modules and by determining functionality using methods akin to design
synthesis. The goal is to make it easier for a human analyst to comprehend the
functionality of an unstructured netlist by identifying as many components as
possible. Holler et al. (re3, ) describe a method that combines image
processing and machine learning to improve the effectiveness and precision of
reverse engineering procedures. Botero et al. have used machine learning
algorithms to recognize patterns and categorize the parts, while image
processing techniques can be used to extract features from photos of the
hardware (re4, ). Recently, there has also been work on discovering the
algorithms to find the specification of the extracted design (re5, ).

Figure 3. ObNoCs implementation environment in Quartus Prime and Platform
Designer

###  2.4. Quartus Environment Basics

Although the ObNoCs infrastructure is independent of the underlying framework
used for designing the NoCs being obfuscated, the platform is integrated with
the Intel Quartus environment and all SoCs discussed in this paper are
designed in Quartus. Quartus is a programmable logic device design software
targeted for the Intel FPGA platform. It is an effective tool for creating
digital circuits and systems on chips in the realm of embedded systems. Design
entry and verification, synthesis, place-and-route, time analysis, and
programming are among the features that it offers. The SoC’s size,
performance, and power consumption can be improved by placing and routing
digital circuits more efficiently thanks to the tool’s sophisticated
algorithms. However, it can be complex to use and requires significant
computational resources. Fig. 3 shows the general Quartus environment
including Platform Designer. The Intel Quartus Prime software includes
Platform Designer, which offers a user-friendly environment for creating and
modifying SoCs. It has an Intel IP library that can be used to create any SoC
design with the ability to add custom logic and set up interfaces in Platform
Designer. Along with options for system configuration and optimization,
Platform Designer offers the flexibility to add any Intel outside IP to the
design. Platform designer automatically creates the NoC interconnect during
SoC generation. The number of routers inside the NoC interconnect varies with
the size of the SoC.

##  3\. ObNoCs Architecture

###  3.1. MUX Insertion Methodology

Our motivating example in Section 1.1 identifies the key ingredients of the
ObNoCs methodology. ObNoCs takes an SoC design (typically in RTL) together
with user directives for routers targeted for obfuscation. The output of the
ObNoCs transformation is a transformed design with the routers obfuscated
through redaction using the _MUX-DEMUX_ switches as discussed above.

Input: Router $\cal{R}$ with source and destination connections
${\cal{R}}[{\cal{S}}_{i}]$, ${\cal{R}}[{\cal{D}}_{i}]$

Output: Activation package for $\cal{R}$ : ${\cal{R}}[{\cal{P}}_{i}]$,
$Act\\_Pkg$ Source (DEMUX) Configuration

1:for single Router connection  ${\cal{R}}$ : ${\cal{R}}[{\cal{S}}_{i}]$ ,
${\cal{R}}[{\cal{D}}_{i}]$. ${\cal{D}}_{i}$ $\leftarrow$ ${\cal{S}}_{i}$

2: for all ${\cal{S}_{i}}$ in ${\cal{R}}[{\cal{S}}]$, do

3: Generate ${MUX}_{{R}\\_S_{i}}$.

4: MUX input :${MUX}_{{R}\\_S_{i}}[{{in}}_{i}]$ $\leftarrow$
${\cal{R}}[{\cal{S}}_{i}]$,

5: MUX output :${MUX}_{{R}\\_S_{i}}[out]$

6: MUX_out_list append ${MUX}_{{R}\\_S_{i}}[out]$

7: Store : ${P_{R}}_{i}=[in_{i},S_{i},D_{i}$,${MUX}_{{R}\\_S_{i}}[out]$ ]

8: RandomizeConnections(${MUX}_{{R}\\_S_{i}}[{{in}}_{i}]$)

9: $Sel_{R}$ $\leftarrow$ getIndex(${{MUX}_{{R}\\_S_{i}}}$, $in_{i}$, $S_{i}$)

10: $Act\\_Pkg[R]$ append $Sel_{R}$

11: end for

12: for all ${\cal{D}_{i}}$ in ${\cal{R}}[{\cal{D}}_{i}]$, do

13: Generate ${MUX}_{{R}\\_D_{i}}$:

14: ${MUX}_{{R}\\_D_{i}}[{in_{i}}]$ append
${P_{R}}_{i}$[${MUX}_{{R}\\_S_{i}}[out]$]

15: ${MUX}_{{R}\\_D_{i}}[{out}]$ $\leftarrow$ ${\cal{R}}[{\cal{D}}_{i}]$

16: end for

17:end for

18:return $Act\\_Pkg$, MUX_out_list

Destination (MUX) Configuration

Input: Router $\cal{R}$ with source and destination connections
${\cal{R}}[{\cal{S}}_{i}]$, ${\cal{R}}[{\cal{D}}_{i}]$,
${MUX}_{{R}\\_S_{i}}[out]$, MUX_out_list.

Output: Activation package for $\cal{R}$ : ${\cal{R}}[{\cal{P}}_{i}]$,
$Act\\_Pkg$

1:for all Router connections  ${\cal{R}_{n}}$ : ,
${\cal{R}_{n}}[{\cal{D}}_{n}]$.

2: MUX input :${MUX}_{{R}_{n}\\_D_{i}}[{{in}}_{i}]$ $\leftarrow$
${MUX}_{{R}_{n}\\_S_{i}}[out]$

3: ${MUX}_{{R}_{n}\\_D_{i}}[{{in}}_{i}-1]$ $\leftarrow$
randomSelect(MUX_out_list, $size$-1)

4: MUX output :${MUX}_{{R}_{n}\\_D_{i}}[out]$

5: RandomizeConnections(${MUX}_{{R}_{n}\\_D_{i}}[{{in}}_{i}]$)

6: $Sel_{R_{n}}$ $\leftarrow$ getIndex($MUX_{R_{n}}$, $in_{i}$ ,
${MUX}_{{R}_{n}\\_D_{i}}[out]$ , $D_{i}$ )

7: $Act\\_Pkg[R_{n}\\_S_{i}]$ append ${Sel_{R}}_{n}$

8: end for

9:return $Act\\_Pkg$

Algorithm 1 Algorithm for Custom MUX Insertion

Algorithm 1 defines the procedure for inserting the MUX-DEMUX switch at each
router ${\cal{R}}$. Roughly, for each ${\cal{S}}_{i}$ such that there is a
link ${\cal{R}}\rightarrow{\cal{S}}_{i}$ and each ${\cal{D}}_{i}$ such that
there is a link ${\cal{D}}_{i}\rightarrow{\cal{R}}$, we instantiate a
programmable MUX for each end of the router links. Here the function
RandomizeConnections introduces non-determinism in connecting the outputs of a
MUX, e.g., in our motivating example, it will enable us to non-
deterministically map the four candidate blocks to the four outputs of the
DEMUX switch for $R_{1}$. Finally, for each MUX insertion, Algorithm 1
additionally records the bit pattern that must be loaded to the control
register to recover the original topology. For the configuration of the MUX on
the Source side as mentioned in Algorithm 1, each input of the generated MUX
(${MUX}_{{R}\\_S_{i}}$) would be connected to all the signals of the Router
outputs ${\cal{R}}[{\cal{S}}_{i}]$. The MUX output would be appended to a
custom array MUX_out_list, which would serve as inputs to the Destination
MUX’s (${MUX}_{{R}\\_D_{i}}$). For the correct transformation involving the
communication links, the MUX select lines have to be configured accordingly,
for which the correct configuration for each Source MUX is stored in a
variable ${P_{R}}_{i}$, with the input Source signal, the intended destination
signal along with the connections of the source MUX
($in_{i},S_{i},D_{i}$,${MUX}_{{R}\\_S_{i}}[out]$), respectively. Using a
RandomizeConnections function, the input signals of the source MUX are
randomized, to increase the uncertainty of retracing in case of reverse
engineering in a brute force attack scenario. The correct MUX configuration,
using the select lines would be retrieved by the array index i.e.the position
of the actual input signal by referring to the signals stored in
${P_{R}}_{i}$. The right select line configuration,$Sel_{R}$, is then appended
to the comprehensive activation package ($Act\\_Pkg[R]$) used to configure our
entire transformation. The bit pattern required for the DEMUX switches (resp.,
MUX switches) at the output (resp. input) ports of router ${\cal{R}}$ will be
referred to as the output (resp. input) activation package for ${\cal{R}}$.
The bit pattern obtained by concatenating the activation packages of all
routers in the NoC will be referred to as the activation package of the NoC,
or simply activation package ($Act\\_Pkg$).

###### Remark 1.

Algorithm 1 inserts MUXes on a port of router ${\cal{R}}$ such that the
control configurations induce topologies involving blocks that are already
connected to some port of ${\cal{R}}$. However, note that the only requirement
for functional correctness is that the intended topology is realized under the
MUX control configurations that correspond to the correct activation package;
no assumption is required for other configurations. ObNoCs can exploit this
observation to connect ${\cal{R}}$ with other IPs creating additional
topologies under different control configuration. This can provide additional
protection against SAT attacks and brute force adversaries.

|
---|---
(a) | (b)
Figure 4. (a) Architecture of the Activation Package Loader Circuit. (b)
Transformed SoC with Integrated Activation Package Loader.

###  3.2. Activation Package Loader

An NoC design transformed by ObNoCs would realize the original topology when
the registers connected to the controls of MUX and DEMUX switches are
configured with the activation package. On the other hand, it is not possible
to load the activation package directly on the fabricated SoC via parallel
load from external inputs given the limited number of input pins available.
ObNoCs correspondingly also introduces circuitry to load the activation
package through a bit-shifting paradigm.

Fig. 4 shows the architecture for loading the activation package. The design
is inspired by scan chain designs in VLSI testing. To streamline insertion, we
create a single register bank, referred to as activation package load register
(AP_LOAD_ REG) for holding the activation package of the NoC.
$AP\\_LOAD\\_REG$ works on the Serial Input Parallel Output (SIPO) mechanism,
where the activation package is provided one bit at a time per each clock
cycle through the $1$-bit primary input $AP\\_in$. The signal $LOAD\\_en$ is
gated with the clock and the bits are loaded into the shift register only when
$LOAD\\_en$ is asserted. Once the entire activation package is loaded into the
register, the $LOAD\\_en$ is then de-asserted and the parallel outputs of the
register are connected to the respective programmable MUX select lines, with
the correct configuration realizing the intended topology.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

Figure 5. Different Functional Topology generation using ObNoCs. 5(a)
indicates the original topology, while the other six topologies are legally
functional, but none of them have the Original Functionality.

##  4\. Security Analysis

###  4.1. Theoretical Guarantee

The key security guarantee of ObNoCs is that the original topology of the NoC
interconnect cannot be derived from the obfuscated design without knowledge of
the activation package. To make this statement formal, let us fix a design
${\cal{D}}$ and let ${\cal{D}}_{o}$ be an obfuscated design generated from
ObNoCs with an $n$-bit activation package $A\in\\{0,1\\}^{n}$. We call the
topology graph ${\cal{T}}$ of ${\cal{D}}$ the intended topology. Obviously,
${\cal{N}}$ consists of the IPs and routers in ${\cal{D}}$. We call any
topology graph ${\cal{G}}$ over ${\cal{N}}$ a legal topology if for any node
$v\in{\cal{N}}$, the degree of $v$ in ${\cal{T}}$ is the same as the degree of
$v$ in ${\cal{G}}$. Given any binary string $b\in\\{0,1\\}^{n}$, we refer to
graph ${\cal{G}}_{b}$ derived from ${\cal{D}}_{o}$ by setting the MUX controls
to be the bitstring $b$ as the topology of ${\cal{D}}_{o}$ induced by $b$.
Obviously, the topology of ${\cal{D}}_{o}$ induced by the activation package
$A$ is the intended topology. Then the following property defines the security
guarantee of ObNoCs.

Legality Enumeration. Given a binary string $b\in\\{0,1\\}^{n}$, let $m$ be
the average degree in the topology of ${\cal{D}}_{o}$ induced by $b$. Then the
total number of unique legal topologies is $m!$.

The property is a straightforward from the ObNoCs construction and the
observation that the connections induced by the MUX and DEMUX switches at the
input and output of each router respect the original in-degree and out-degree
of each node. A consequence of the property is that the intended topology
${\cal{T}}$ is different from all the other legal topologies induced by the
obfuscated design ${\cal{D}}_{o}$ only by the specifics of the bitstream that
defines the activation package $A$. It follows that an adversary without
access to $A$, cannot distinguish the intended topology from other legal
topologies.

Figure 6. Schematic of an NoC interconnect in Xilinx Vivado along with an ALU

Figure 7. Multiple DUTs for the same Obfuscated NoC to compare the output for
different activation package combination

###### Remark 2.

Informally, the intended topology here is really the topology that the
designer desires, while all topologies that can be realized through some
values of the configuration bitstream are legal topologies. It follows that
the intended topology is simply one of the legal topologies, in particular the
specific legal topology that corresponds to the activation package that the
designer has in mind. However, other than the specifics of the activation
package there is nothing else to distinguish the intended topology from other
(unintended) ones. In particular, each legal topology would constitute an SoC
in which IPs could communicate with one another. Note that some values of the
configuration bitstream would result in a non-functional topology in the sense
that the same port of two IPs is mapped to the same output. Fig. 5 shows some
possible unintended and non-functional topologies, together with the (unique)
intended topology. It is obvious that an adversary can detect non-functional
bit configurations; however, a large number of legal topologies and the
uniqueness of the intended topology among the legal ones implies that
identifying the intended topology is equivalent to identifying the activation
package.

To explain the consequences of the above analysis a bit further, consider the
SoC design shown in Fig. 1 For each router obfuscation, we used $16$ 4x1 MUXs.
Since each 4x1 MUX requires two select lines, the total number of bits for the
activation package is $32$. However, not every bit pattern corresponds to a
unique legal topology, due to the recombination of the combinational logic
involved. Even if only one router is obfuscated for the design in Fig. 1, the
number of legal topologies is $4!=24$. Fig. 5 illustrates $7$ of the $24$
possible topologies (including the intended one) whereas Fig. 5(a) indicates
the intended topology upon insertion of the correct activation package. The
four different colored arrows in the red encircled portion with router $R_{1}$
indicates the original connection with the $R_{3}$, $R_{4}$, $R_{5}$ and
$IP_{6}$. These connections from $R_{1}$ can be controlled by our ObNoCs which
has been depicted in the rest of the figures in Fig. 5. On the other hand,
there is no a priori reason to determine which one of the legal topologies is
the intended one (from a functional standpoint) other than the
“idiosyncrasies” of the designer’s choice. Furthermore, as our empirical
evaluation shows (see below) the different legal topologies induce very
different computations; consequently, the adversary cannot get away with
identifying a topology close enough to the intended. Finally, the number of
possible legal topologies can be compounded by simply composing the
obfuscation in stages: for a 2-stage MUX-based obfuscation from Fig. 2, there
are $4!\cdot 4!=576$ legal topologies.

We conclude this section with a brief comment on the storage of the activation
package. Recall that our threat model considers an untrusted foundry or
testing facility that has access to the layout information for the
unfabricated SoC as well as silicon implementation of the fabricated SoC.
Since the topology information is redacted by ObNoCs through the MUX insertion
and the control bits of the MUX are only programmed subsequently with the
activation package by the OEM, neither the layout nor the fabricated SoC has
the activation package stored in the chip as long as the SoC is in control of
the untrusted entity. However, when the SoC goes to field, it includes the
activation package (which is obviously required to make the SoC functional).
In this paper, we do not specifically discuss the storage of the activation
package in field since it is outside the scope of our threat model. However,
ObNoCs does not need any specialized mechanism for storage and application of
activation package; any mechanism for storing keys used for unlocking an
obfuscated circuit (e.g., through logic locking) can be applied for this
purpose, e.g., a typical mechanism involves utilizing a small tamper-proof ROM
in the design to hold the key bits.111Current state-of-the-art locking
techniques generally use an on-chip ROM although techniques for storing the
key in the cloud together with other provisioned assets is being explored.
Generally, the requirement is that the storage should be tamper-proof and
communication of the key for its application should satisfy non-observability
requirements.

Figure 8. Comparison of the Output of all 9 DUTs on nine different activation
package insertion

###  4.2. Resiliency Against Known Attacks on MUX-based Obfuscation

MUX-based transformation is a common strategy for obfuscating hardware
functionality. Correspondingly, there has been significant research on attacks
against such obfuscation. To demonstrate the effectiveness of ObNoCs we
consider some common attack strategies and explain how ObNoCs provides
resiliency against these attacks.

###### Remark 3.

Note that there has been no previous work to our knowledge on obfuscation of
NoC topologies. Although traditional logic locking techniques can be applied
to SoC designs with NoC fabrics, they are generally applicable only to gate-
level netlists. Performing them on a complete SoC, while possible in
principle, incurs significant computational overhead and is infeasible in
practice. Indeed, ObNoCs avoids netlist designs works on RTL-level designs to
avoid such computational overhead in obfuscation. Furthermore, the presence of
encrypted IPs in Quartus makes it practically infeasible to extract a complete
netlist from Quartus to enable a direct comparison with other obfuscation
techniques. Furthermore, given these factors, a direct implementation and
evaluation of traditional attacks (which also apply to gate-level netlists)
could not be performed as part of direct resiliency evaluation. However,
ObNoCs architecture in spite of being a MUX-based framework, is robust against
typical attacks on MUX-based obfuscation techniques as explained below.

##### ML-based Attacks

Machine Learning attacks on obfuscation (alrahis2022muxlink, ; alaql2019sweep,
) use a variety of ML techniques to predict MUX configurations, thereby
inferring unbofuscated links, e.g., Alrahis et al. (alrahis2022muxlink, ) use
GNN to perform such predictions. However, the success of the attacks relies on
the fact that the obfuscation is performed on a netlist post synthesis.
Correspondingly, the ML strategies are employed on unobfuscated links
indicating dependence on the technology library. However, in ObNoCs, this
assumption is broken since the obfuscation is performed before synthesis and
MUXs used are architectural entities with no dependence on the underlying
technology library for insertion.

##### SAT Attacks

SAT attacks (sat-logic-locking, ) form another popular class of attacks to
break hardware obfuscation. They depend on an oracle (e.g., a fabricated
design on which one can execute test patterns) to answer the sequence of SAT
queries. The SAT queries are computed to enable reconstruction of specific
bits of the activation package. Resiliency against SAT attacks depends on the
query complexity, i.e., the number of SAT queries involved in the attack. For
ObNoCs, the query complexity is defined by the number of legal topologies
derived in Section 4.1. Furthermore, recall that ObNoCs enables extensibility
by extending the number of router connections with additional IPs, which can
be applied to achieve additional resiliency to SAT attacks. Finally, since SAT
attack (and other attacks) cannot distinguish the intended topology from other
legal topologies, the correct activation package even if produced as a
candidate bit pattern through SAT attack, cannot be vetted as indeed inducing
the intended topology (see below).

##### Specific Attack Instances

We have analyzed the resilience of ObNoCs on two specific attack instances:
(1) redundancy-based attack strategy (redundancy, ), and (2) the SNAPSHOT deep
learning attack (snapshot, ). The key idea of redundancy-based strategy is
that an incorrect activation package would lead to incorrect functionality,
which is exploited through different redundancy levels to infer the correct
key. SNAPSHOT relies on a deep learning strategy to predict the correct
activation package that corresponds to “intended” functionality. However, for
ObNoCs, legal topologies that differ from the intended one would still produce
a functional SoC, simply not the one intended by the SoC designer.
Consequently, since the technique relies on functional validation to detect
incorrect behavior, it cannot distinguish counterfeit SoCs with legal
topologies from the intended one.

###### Remark 4.

Obviously, any of the strategies above can find legal topologies. This leaves
open the possibility that the adversary can simply enumerate (and fabricate)
all counterfeit SoC variants corresponding to legal topologies. This is indeed
a threat if the number of legal topologies is small. However, as discussed
above, ObNoCs can apply staging strategy to expand the space of legal
topologies by multiplicative factors. Note that adding a single stage would
multiply the number of legal topologies by a factor of $24$. Indeed, simply
using the 2-stage strategy of Fig. 2 with $576$ possible legal topologies
makes it infeasible for the adversary to fabricate all the SoC variants.

(a)

MultiSoC

(b)

LUTSoC

(c)

FlashSoC

Figure 9. Three SoC designs Used for ObNoCs Evaluation. All three designs have
been implemented on Quartus Prime with Platform Designer.

###  4.3. Empirical Analysis

The security analysis above shows that it is infeasible for the adversary to
reverse-engineer the intended topology from ObNoCs obfuscation. One objection
to that thesis could be that many topologies could be functionally similar, so
a counterfeit SoC that does not create the intended topology could still serve
as a valid counterfeit. To evaluate this possibility, we considered the a NoC
interconnect and created a simulation environment with an ALU module
integrated for effective analysis of the functionality. Fig. 6 shows a Xilinx
Vivado setup for this empirical analysis.222Our primary design and
experimental testbed is Quartus, which we used for overhead analysis as
discussed in Section 5. In this figure, the router including all the MUXes
used for this obfuscation, and the ALU module have been highlighted for a
better understanding of the design. However, for the empirical security
analysis, we used Vivado for ease of simulation of different instances. The
interconnect model was exported from Platform Designer to Vivado to perform
this simulation. In this figure, the router including all the required MUXes
for the obfuscation and the ALU module have been pointed out for a better
understanding of the design. The key idea is to drive the interconnect with
different workloads corresponding to inter-IP communications and observe the
functional impact on the computation of the ALU. The simulation used a total
of $9$ DUTs (Fig. 7) of which only one is driven by the correct activation
package while the rest are incorrect. Fig. 8 shows the result of the
simulation. The correct functionality is derived only with the correct
activation package. In the simulation we have provided 9 different activation
package for 9 DUTs. On the other hand, the ALU is still functional (but
incorrect and different from the functionality in the intended topology) in
$6$ DUTs, which correspond to legal topologies different from the intended
one. Note that functional validation of the ALU would consider all $7$
topologies to be correct, thwarting attacks that depend on functional
validation.

Recall that the theoretical analysis above showed that the obfuscated design
can correspond to a number of different legal topologies of which only one is
the intended one. To substantiate this, we have created a simulation
environment in Xilinx Vivado. For this simulation, we have taken only the
interconnect generated in Platform Designer as our Design Under Test (DUT).

The interconnect has been shown in Fig. 6 and we have integrated one ALU
module in it for better analysis. The NoC interconnect fabric is responsible
for all the data communication for the SoC. To check data transfer from the
NoC, we have taken the ALU result as our reference. In our simulation, there
are total 9 DUTs in Fig. 7 where only one of them is driven by the correct
activation package, 8 are driven by the incorrect activation package.

##  5\. Overhead Analysis

###  5.1. Benchmark SoCs

A key challenge in research on SoC security validation is the lack of an
appropriate testbed for evaluation. Evaluation of ObNoCs requires SoC designs
with a realistic NoC-based communication fabrics connecting disparate IP cores
that reflect realistic design complexity. Unfortunately, there is no open-
source SoC design satisfying these requirements. To address this problem, we
have developed our own SoC benchmarks, shown in Fig. 9. We use three SoCs with
different interconnect sizes to ensure that our results are generalizable. The
three SoCs are derivatives of each other, comprised of similar IPs but with
different interconnect topologies. We refer to the SoCs as MultiSoC, LUTSoC,
and FlashSoC.

respectively. Each SoC is comprised of six subsystems, with each subsystem
containing specific IPs; The CPU subsystem is made up of two NIOS processors;
the memory subsystem consists of an on-chip memory and a DMA controller; the
Communication subsystem includes an SPI module, an Ethernet, and a Serial
Flash module; and the Debugging subsystem consists of a JTAG and a Performance
Counter IP.

While undoubtedly simple compared to an industrial product, the SoCs are non-
trivial; the RTL for the unobfuscated (original) SoC for each variant runs to
about $100,000$ lines of RTL, with the interconnect fabric accounting for
$10,500$ lines. The Block Memory bits for the SoCs are $3.6\times 10^{5}$,
$9.8\times 10^{5}$, and $1.2\times 10^{6}$ respectively, and there are
respectively $12$, $15$ and $16$ routers in the NoC fabrics.

Figure 10. Schematic of Benchmark SoC in Fig. 9(a) from Quartus along with the
obfuscated Interconnect using ObNoCs technique

###  5.2. Platform and Implementation Details

We implemented ObNoCs using the Intel Quartus Pro 21.3. For our SoC design and
integration, we have used the Platform Designer frontend of Quartus and
implemented the ObNoCs methodology for systematically redacting various router
connections as reported below. For evaluating ObNoCs, we have designed the
SoCs using the Platform Designer (PD) frontend of Quartus Pro 21.3 and
implemented on the Agilex F Series FPGA, AGFA012R24A2E2V. Fig. 10 shows the
schematic diagram of the obfuscated SoC where the enclosed red rectangle
indicates the NoC interconnect of the SoC after transformation by ObNoCs.

(a) ALM

(b) MLAB

Figure 11. ALM and MLAB Architecture in Intel® Agilex™ 7 FPGAs

###  5.3. Result Analysis

To provide a fine-grained analysis of the overhead induced by our interconnect
transformation, we define five levels of obfuscation (0-IV) as shown in Table
1 where obfuscation level 0 indicates no obfuscation, i.e., the original
design. Estimates of power and hardware resource overheads have been derived
from the Quartus platform. Quartus provides three different metrics on the
resource overhead: (1) power consumption; (2) number of required Adaptive
Logic Modules (ALMs) and (3) number of Logic registers (which estimates the
state elements). The Intel Agilex device consists of Logic Array Blocks (LABs)
shown in Fig. 11(b) and is implemented by enhanced ALM modules mentioned in
Fig. 11(a) which allows efficient implementation of logic functions. Each ALM
consists of two Adaptive Look-up Tables (ALUTs), two dedicated embedded Adders
and four dedicated Registers (agilexfpga, ). We have followed the user
guidelines from (qprime, ) to carefully analyze the resources from Quartus
generated reports.

Table 1. Obfuscation Level based on No. of Routers Obfuscation Level | 0 | I | II | III | IV
---|---|---|---|---|---
No. of Routers | 0 | 2 | 4 | 8 | 16

(a) Power (W)

(b) Number of ALM

(c) Number of Logic Registers

Figure 12. Resource Analysis for MultiSoC, LUTSoC and FlashSoC at different
obfuscation level

(a) MultiSoC

(b) LUTSoC

(c) FlashSoC

Figure 13. Resource Overhead Rate for all 3 SoCs at different obfuscation
levels.

Figs. 12(a), 12(b) and 12(c) show the resource utilization for different
levels of obfuscation. Since for each obfuscation level there are variations
in utilization depending on which specific routers are selected as obfuscation
targets (see below), we consider the average utilization for each combination,
e.g., the resource overhead for Obfuscation Level I is calculated by
considering the $n\choose 2$ results for designs derived by obfuscating each
possible pair of routers and considering the arithmetic mean where $n$ is the
number of routers available inside the NoC fabric. Power and number of ALM
both are increasing with the obfuscation level for all three SoCs MultiSoC,
LUTSoC and FlashSoC. Note that the power and number of ALM units are
increasing with the obfuscation level increment whereas the number of logic
registers are decreasing.333We have taken the ALM and Logic Registers values
obtained from Quartus synthesis report to represent area overhead. Note that
it is not possible to export the netlist synthesized from Quartus to an
external environment (e.g., Xilinx Vivado or Synopsys Design Compiler) since
the Quartus environment integrates a number of encrypted IPs. Consequently,
area estimation using those traditional tools is not possible. For an ASIC
implementation, the overhead result can be different.

Figs. 13(a), 13(b) and 13(c) show the resource overhead rate results
corresponding to various obfuscation levels for the three designs. Note that
this results in an average of only 5.68% overhead increase in the number of
ALM modules, 2.41% overhead increase in power consumption, 23.46% reduction in
usage of logic registers, where all of the three resource parameters have been
compared with their respective unobfuscated designs. Nevertheless, we can
conclude that the addition of logic by ObNoCs appreciably impacts very little
in resource overhead.

It is interesting to understand the decrease in the logic register overhead
which can be attributed to the increase in the number of ALMs, with each ALM
consisting of 4 additional registers. Since the obfuscation technique is
implemented using pure combinational logic, the primary effect of the overhead
is an increase in the number of ALMs as well as total power. This
combinational logic is implemented with ALMs, which leaves fewer resources
available to build logic registers. In general, all of the design’s logic
functions, including both combinational and sequential logic, must share the
resources in an FPGA, such as ALMs and flip-flops. Additionally, the number of
flip-flops that can be used to build the registers are constrained if the
combinational logic calls for a large number of inputs or outputs.
Furthermore, additional combinational logic introduced during obfuscation
(e.g., MUX and DEMUX structures) permits Quartus to perform aggressive
optimizations in logic synthesis.

Finally, the additional hardware logic introduced for obfuscation may affect
the critical path of the system. From Fig. 14, we observe that the critical
path increases due to the obfuscation level. This suggests that the increased
security due to the increasing degree of obfuscation induces a trade-off by
adding combinational gate delay. However, the delay induced is significant
only for obfuscation levels III and IV. Furthermore, in SoCs with a larger
number of IPs, the combinational delay in the interconnect would be
proportionately less. This timing resource analysis is solely based on Quartus
Timing Analyzer report (qprime, ) with considering slack and critical path as
timing parameters.444Our observations are based on pre-synthesis estimates,
which can be different from post-synthesis implementation. Implementing ObNoCs
in FPGA and considering the correlation between pre-synthesis and post-
synthesis timing correlation will be considered in future work. However, such
correlations are not germane to ObNoCs and follow standard practice of timing
correlations between various timing models used pre-synthesis vis-a-vis timing
on actual artifacts.

Figure 14. Timing Analysis for LUTSoC at different obfuscation levels.

##  6\. Related Work

There has been significant research on hardware obfuscation techniques
primarily for protecting hardware IPs against theft, reverse engineering,
structural, data integrity and eavesdropping attacks. Logic locking methods
provide enhanced IP security by introducing additional logic to the design
(chakraborty2010rtl, ), (yasin2017provably, ),(alaql2019sweep, ). Logic
locking technique has been used for protecting integrated IPs in modern SoC
architectures from various hardware security threats. While extensive research
has been conducted on the applicability and effectiveness of logic locking
over the past decade, the security and strength of existing techniques remain
questionable due to evolving attacks(cryptoeprint:2022/260, ). State Space
Obfuscation techniques additionally include extra state elements to obfuscate
the finite state machines (chakraborty2009harpoon, ). Correspondingly there
has been work on attacking various logic-locking schemes based on SAT-based
attacks (sat-logic-locking, ) and defenses proposed against such attacks
(meade2016gate, ), (yasin2016sarlock, ), (yasin2015improving, ). Paar et al.
(paar, ) developed two foundry-level invasive attack schemes based on probing
and mask modification which could be used to break the encryption. Other
advanced attempts to break obfuscation schemes have been proposed
(Albartus2020dana, ). As machine learning spreads, new strategies for breaking
logic-locking systems have emerged. this paper Sisejkovic et al. (9606979, )
presents an overview of current breakthroughs in logic-locking attacks and
defenses. Many logic locking systems now in use have a flaw that can be
exploited by an attacker to recover key bits from the locked chip’s design
without the need for a working replica of the device. Massad et al.
(DBLP:journals/corr/MassadZGT17, ) suggests a new logic locking method,
Meerkat, to solve this weakness and ensure security by utilizing Reduced
Ordered Binary Decision Diagrams.

Shamsi et al. (10.1145/3194554.3194580, ) introduced an interconnect locking
scheme based on cross bars and layout inclusive. But this technique is
targeted only for IPs rather than a complete SoC. Kolbe et al. (9586242, )
proposed a dynamic obfuscation technique by using reconfigurable logic and
interconnect blocks (RIL-Blocks) from the emerging spin-based devices. This
technique is robust against the SAT attacks but is only feasible for the
devices with Magnetic Random Access Memory (MRAM). By using fully programable
Logic and Routing block (PLR), Kamali et al. proposed a Full-Lock obfuscation
technique (10.1145/3316781.3317831, ). Shamsi et al. (10.1145/3060403.3060458,
) introduced dummy paths to the circuit to get the cyclic obfuscation which is
also robust against SAT attack. Zhang et al. (zhang2023csar, ) offers C-SAR, a
security architecture to protect against SAT attacks. By expanding the key
search space and extending the clock cycles of attack inputs, C-SAR protects
against SAT attacks. They demonstrate that the cost of C-SAR is controllable
because it only rises linearly as a function of key bits. Juretus et al.
provide analysis on the performance of a different obfuscation technique
against SAT attack (8747381, ). The obfuscation technique has also been
applied at the post-fabrication level using the post-fabrication Transistor
Level Programming (TRAP) which can stand against both brute-force and oracle-
guided SAT attacks (8714856, ).

Authenticated encryption schemes for NoC security (gebotys2003framework,
),(sepulveda2017towards, ),(charles2020securing, ), focus on the encryption-
decryption of the data packets emanating out of an IP in the SoC. Deb Nath et
al. (tifs20, ) proposed an architecture-level solution for run-time detection
of security-critical events in SoC designs with NoC fabrics by implementing
security policies implemented through a specialized security-policy engine.
Securing inter-IP communications by detection of security policy violations by
Meng et al. (9785862sevnoc, ) developed a property-based model comparison
strategies to validate the NoC communications against information flow
violations. There has been work on mitigating the effects of data integrity
and hardware Trojans in NoC designs (jyv2018run, ; ancajas2014fort, ). Wassel
et al. (wassel2013surfnoc, ) developed techniques to increase security by
temporal partitioning of data into different domains. Route randomization
techniques have also been employed to detect and mitigate various side channel
attacks (reinbrecht2016gossip, ), (reinbrecht2016side, ),
(reinbrecht2020guard, ), (indrusiak2017side, ),(indrusiak2019side, ).

##  7\. Conclusion and Future Work

We have developed a new methodology, ObNoCs, for redacting NoC topologies in
SoC designs to protect against reverse engineering by untrusted fabrication
facilities. To our knowledge, ObNoCs represents the first technique for
redacting system-level functionality in SoC designs. ObNoCs systematically
replaces router connections with switches that can be programmed after
fabrication. We show how to implement this redaction functionality efficiently
using MUX and DEMUX logic. Our experimental results on representative SoC
implementations show that the resource and overhead of transformations through
ObNoCs is minimal. Furthermore, ObNoCs provides provable obfuscation of NoC
connection against reverse-engineering adversaries.

In future work, we plan to apply ObNoCs on industrial-scale SoC designs. We
plan to increase the level of redaction by replacing the routing tables with
custom configurable registers leading to enhanced security. We also plan to
extend our implementation of ObNoCs into a fully automated CAD infrastructure.

#### Acknowledgements

This research has been partially supported by the Defense Advanced Research
Projects Agency under the SAHARA Program, Contract No. HR0011-21-3-0001. We
thank Kostas Amberiadis for his advice and help during the project, and the
Intel Quartus team for help with numerous Quartus issues.

## References

  * [1] Intel baytrail products.  https://ark.intel.com/content/www/us/en/ark/products/codename/55844/bay-trail.html.
  * [2] Intel Quartus Prime Software.  https://www.intel.com/content/www/us/en/products/details/fpga/development-tools/quartus-prime.html/.  [Online].
  * [3] Intel® agilex™ i-series fpga and soc fpga.  https://www.intel.com/content/www/us/en/products/details/fpga/agilex/i-series/docs.html.
  * [4] A. Abdulrahman, A. S. Abuadbba, A. Aldabbagh, and O. Hasan.  Sweep to the secret: A constant propagation attack on logic locking.  In Proceedings of the 2019 IEEE Asian Hardware-Oriented Security and Trust Symposium (AsianHOST), pages 1–6. IEEE, 2019.
  * [5] N. Albartus, A. Bayrak, and M. Zohner.  Dana universal dataflow analysis for gate-level netlist reverse engineering.  IACR Transactions on Cryptographic Hardware and Embedded Systems, 2020(2):129–155, 2020.
  * [6] L. Alrahis, S. Patnaik, M. Shafique, and O. Sinanoglu.  Muxlink: Circumventing learning-resilient mux-locking using graph neural network-based link prediction.  pages 694–699, 2021.
  * [7] D. M. Ancajas, H. J. Perez, J. A. Garcia, P. J. Isidro, J. J. Garcia, M. A. Marcelino, R. Salvador, R. Villanueva, and P. J. Flores.  Fort-NoCs: Mitigating the threat of a compromised noc.  In Proceedings of the 51st Annual Design Automation Conference (DAC), pages 1–6, 2014.
  * [8] L. Azriel, J. Speith, N. Albartus, R. Ginosara, A. Mendelson, and C. Paar.  A survey of algorithmic methods in ic reverse engineering.  Cryptology ePrint Archive, Paper 2021/1278, 2021.  https://eprint.iacr.org/2021/1278.
  * [9] U. J. Botero, R. Wilson, H. Lu, M. T. Rahman, M. A. Mallaiyan, F. Ganji, N. Asadizanjani, M. M. Tehranipoor, D. L. Woodard, and D. Forte.  Hardware trust and assurance through reverse engineering: A tutorial and outlook from image analysis and machine learning perspectives.  J. Emerg. Technol. Comput. Syst., 17(4), jun 2021.
  * [10] R. S. Chakraborty and S. Bhunia.  Harpoon: An obfuscation-based soc design methodology for hardware protection.  IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 28(1):97–109, 2009.
  * [11] R. S. Chakraborty and S. Bhunia.  Rtl hardware ip protection using key-based control and data flow obfuscation.  In 2010 23rd International Conference on VLSI Design, pages 405–410, 2010.
  * [12] S. Charles and P. Mishra.  Securing network-on-chip using incremental cryptography.  In Proceedings of the IEEE Computer Society Annual Symposium on VLSI (ISVLSI), pages 53–58. IEEE, 2020.
  * [13] A. P. Deb Nath, S. Kumar, and S. Mukherjee.  Security assurance of system-on-chip designs with NoC fabrics.  IEEE Signal Processing Society Newsletter, 37(5):31–36, 2020.
  * [14] S. Engels, F. A. El-Moussa, J. Rosenblatt, A. Homescu, T. Schneider, and S. Katzenbeisser.  The end of logic locking? a critical view on the security of logic locking.  IACR Cryptology ePrint Archive, 2019:747, 2019.
  * [15] C. Gebotys and R. Gebotys.  A framework for security on noc technologies.  In IEEE Computer Society Annual Symposium on VLSI, 2003. Proceedings., pages 113–117, 2003.
  * [16] H. Gomez, C. Duran, and E. Roa.  Defeating silicon reverse engineering using a layout-level standard cell camouflage.  IEEE Transactions on Consumer Electronics, 65(1):109–118, 2019\.
  * [17] K. Hofmann.  Network-on-chip: Challenges for the interconnect and i/o-architecture.  In 2012 International Conference on High Performance Computing & Simulation (HPCS), pages 252–253, 2012.
  * [18] M. Holler, M. Odstrcil, M. Guizar-Sicairos, M. Lebugle, E. Müller, S. Finizio, G. Tinti, C. David, J. Zusman, W. G. Unglaub, O. Bunk, J. Raabe, A. F. J. Levi, and G. Aeppli.  Three-dimensional imaging of integrated circuits with macro- to nanoscale zoom.  Nature Electronics, 2:464 – 470, 2019.
  * [19] L. S. Indrusiak, J. Harbin, and M. J. Sepulveda.  Side-channel attack resilience through route randomisation in secure real-time networks-on-chip.  In 2017 12th International Symposium on Reconfigurable Communication-centric Systems-on-Chip (ReCoSoC), pages 1–8, 2017.
  * [20] K. Juretus and I. Savidis.  Characterization of in-cone logic locking resiliency against the sat attack.  IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 39(8):1607–1620, 2020.
  * [21] M. K. Jyv, A. K. Swain, K. SudeendraKumar, S. R. Sahoo, and K. K. Mahapatra.  Run time mitigation of performance degradation hardware trojan attacks in network on chip.  pages 738–743, 2018.
  * [22] H. M. Kamali, K. Z. Azar, F. Farahmandi, and M. Tehranipoor.  Advances in logic locking: Past, present, and prospects.  Cryptology ePrint Archive, Paper 2022/260, 2022.  https://eprint.iacr.org/2022/260.
  * [23] H. M. Kamali, K. Z. Azar, H. Homayoun, and A. Sasan.  Full-lock: Hard distributions of sat instances for obfuscating circuits using fully configurable logic and routing blocks.  In Proceedings of the 56th Annual Design Automation Conference 2019, DAC ’19, New York, NY, USA, 2019. Association for Computing Machinery.
  * [24] G. Kolhe, S. Salehi, T. D. Sheaves, H. Homayoun, S. Rafatirad, M. P. D. Sai, and A. Sasan.  Securing hardware via dynamic obfuscation utilizing reconfigurable interconnect and logic blocks.  In 2021 58th ACM/IEEE Design Automation Conference (DAC), pages 229–234, 2021.
  * [25] L. Li and A. Orailoglu.  Redundancy attack: Breaking logic locking through oracleless rationality analysis.  IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 42(4):1044–1057, 2023.
  * [26] M. E. Massad, J. Zhang, S. Garg, and M. V. Tripunitara.  Logic locking for secure outsourced chip fabrication: A new attack and provably secure defense mechanism.  ArXiv, abs/1703.10187, 2017.
  * [27] T. Meade, Y. Jin, M. Tehranipoor, and S. Zhang.  Gate-level netlist reverse engineering for hardware security: Control logic register identification.  In 2016 IEEE International Symposium on Circuits and Systems (ISCAS), pages 1334–1337, 2016.
  * [28] X. Meng, K. Raj, S. Ray, and K. Basu.  Sevnoc: Security validation of system-on-chip designs with noc fabrics.  IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 42(2):672–682, 2023.
  * [29] A. Pathania and J. Henkel.  Task scheduling for many-cores with s-nuca caches.  In 2018 Design, Automation & Test in Europe Conference & Exhibition (DATE), pages 557–562, 2018.
  * [30] C. Reinbrecht, P. Puschner, and C. Steger.  Guard-noc: A protection against side-channel attacks for mpsocs.  In Proceedings of the IEEE Computer Society Annual Symposium on VLSI (ISVLSI), pages 47–52. IEEE, 2020.
  * [31] C. Reinbrecht, P. Puschner, C. Steger, and T. Krieg.  Gossip noc–avoiding timing side-channel attacks through traffic management.  In Proceedings of the IEEE Computer Society Annual Symposium on VLSI (ISVLSI), pages 197–202. IEEE, 2016.
  * [32] C. Reinbrecht, A. Susin, L. Bossuet, G. Sigl, and J. Sepúlveda.  Side channel attack on noc-based mpsocs are practical: Noc prime+probe attack.  In 2016 29th Symposium on Integrated Circuits and Systems Design (SBCCI), pages 1–6, 2016.
  * [33] J. Sepúlveda, A. Zankl, D. Flórez, and G. Sigl.  Towards protected mpsoc communication for information protection against a malicious noc.  Procedia Computer Science, 108:1103–1112, 2017.  International Conference on Computational Science, ICCS 2017, 12-14 June 2017, Zurich, Switzerland.
  * [34] K. Shamsi, M. Li, T. Meade, Z. Zhao, D. Z. Pan, and Y. Jin.  Cyclic obfuscation for creating sat-unresolvable circuits.  In Proceedings of the on Great Lakes Symposium on VLSI 2017, GLSVLSI ’17, page 173–178, New York, NY, USA, 2017. Association for Computing Machinery.
  * [35] K. Shamsi, M. Li, D. Z. Pan, and Y. Jin.  Cross-lock: Dense layout-level interconnect locking using cross-bar architectures.  In Proceedings of the 2018 on Great Lakes Symposium on VLSI, GLSVLSI ’18, page 147–152, New York, NY, USA, 2018. Association for Computing Machinery.
  * [36] M. M. Shihab, J. Tian, G. R. Reddy, B. Hu, W. Swartz, B. Carrion Schaefer, C. Sechen, and Y. Makris.  Design obfuscation through selective post-fabrication transistor-level programming.  In 2019 Design, Automation & Test in Europe Conference & Exhibition (DATE), pages 528–533, 2019.
  * [37] D. Sisejkovic, F. Merchant, L. M. Reimann, H. Srivastava, A. Hallawa, and R. Leupers.  Challenging the security of logic locking schemes in the era of deep learning: A neuroevolutionary approach.  J. Emerg. Technol. Comput. Syst., 17(3), may 2021.
  * [38] D. Sisejkovic, L. M. Reimann, E. Moussavi, F. Merchant, and R. Leupers.  Logic locking at the frontiers of machine learning: A survey on developments and opportunities.  In 2021 IFIP/IEEE 29th International Conference on Very Large Scale Integration (VLSI-SoC), pages 1–6, 2021.
  * [39] I. L. Soares, C. A. M. Pereira, and L. Carro.  Side-channel protected MPSoC through secure real-time networks-on-chip.  Microprocessors and Microsystems, 68:102888, 2019.
  * [40] P. Subramanyan, S. Bhunia, and D. Mukhopadhyay.  Evaluating the security of logic encryption algorithms.  In 2015 IEEE International Symposium on Hardware Oriented Security and Trust (HOST), pages 112–117. IEEE, 2015.
  * [41] P. Subramanyan, N. Tsiskaridze, W. Li, A. Gascón, W. Y. Tan, A. Tiwari, N. Shankar, S. A. Seshia, and S. Malik.  Reverse engineering digital circuits using structural and functional analyses.  IEEE Transactions on Emerging Topics in Computing, 2(1):63–80, 2014\.
  * [42] R. Torrance and D. James.  The state-of-the-art in semiconductor reverse engineering.  In 2011 48th ACM/EDAC/IEEE Design Automation Conference (DAC), pages 333–338, 2011.
  * [43] H. M. G. Wassel, Y. Gao, J. K. Oberg, T. Huffmire, R. Kastner, F. T. Chong, and T. Sherwood.  Surfnoc: A low latency and provably non-interfering approach to secure networks-on-chip.  SIGARCH Comput. Archit. News, 41(3):583–594, jun 2013.
  * [44] M. Yasin, B. Mazumdar, J. Rajendran, and O. Sinanoglu.  Sarlock: Sat attack resistant logic locking.  In Proceedings of the 2016 IEEE International Symposium on Hardware Oriented Security and Trust, HOST 2016, pages 236–241. Institute of Electrical and Electronics Engineers Inc., June 2016.
  * [45] M. Yasin, J. Rajendran, O. Sinanoglu, and R. Karri.  On improving the security of logic locking.  IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 35(9):1411–1424, Sept. 2016.  Publisher Copyright: © 1982-2012 IEEE.
  * [46] M. Yasin, A. Sengupta, M. T. Nabeel, M. Ashraf, J. J. Rajendran, and O. Sinanoglu.  Provably-secure logic locking: From theory to practice.  In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS ’17, page 1601–1618, New York, NY, USA, 2017. Association for Computing Machinery.
  * [47] J. Zhang, P. Bogdan, and S. Nazarian.  C-sar: Sat attack resistant logic locking for rsfq circuits.  ArXiv, abs/2301.10216, 2023.


# Depth of some special monomial ideals

Dorin Popescu and Andrei Zarojanu  Dorin Popescu, ”Simion Stoilow” Institute
of Mathematics of Romanian Academy, Research unit 5, P.O.Box 1-764, Bucharest
014700, Romania<EMAIL_ADDRESS>Andrei Zarojanu, Faculty of Mathematics
and Computer Sciences, University of Bucharest, Str. Academiei 14, Bucharest,
Romania, and  ”Simion Stoilow” Institute of Mathematics of Romanian Academy,
Research group of the project ID-PCE-2011-1023, P.O.Box 1-764, Bucharest
014700, Romania<EMAIL_ADDRESS>
###### Abstract.

Let $I\supsetneq J$ be two squarefree monomial ideals of a polynomial algebra
over a field. Suppose that $I$ is generated by one squarefree monomial of
degree $d>0$, and other squarefree monomials of degrees $\geq d+1$. If the
Stanley depth of $I/J$ is $\leq d+1$ then almost always the usual depth of
$I/J$ is $\leq d+1$ too.

Key words  : Monomial Ideals, Depth, Stanley depth.
2000 Mathematics Subject Classification: Primary 13C15, Secondary 13F20,
13F55, 13P10.

The support from grant ID-PCE-2011-1023 of Romanian Ministry of Education,
Research and Innovation is gratefully acknowledged.

## Introduction

Let $S=K[x_{1},\ldots,x_{n}]$ be the polynomial algebra in $n$ variables over
a field $K$ and $I\supsetneq J$ two squarefree monomial ideals of $S$. Suppose
that $I$ is generated by squarefree monomials of degrees $\geq d$ for some
positive integer $d$. Modulo a multigraded isomorphism we may assume either
that $J=0$, or $J$ is generated in degrees $\geq d+1$. Then
$\operatorname{depth}_{S}I/J\geq d$ (see [1, Proposition 3.1], [3, Lemma 1.1])
and upper bounds are given by Stanley’s Conjecture if it holds. Finding such
upper bounds is the subject of several papers [2], [3], [4], [7], [5]. We
remind below the notion of Stanley depth.

Let $P_{I\setminus J}$ be the poset of all squarefree monomials of $I\setminus
J$ with the order given by the divisibility. Let ${\mathcal{P}}$ be a
partition of $P_{I\setminus J}$ in intervals $[u,v]=\\{w\in P_{I\setminus
J}:u|w,w|v\\}$, let us say $P_{I\setminus J}=\cup_{i}[u_{i},v_{i}]$, the union
being disjoint. Define
$\operatorname{sdepth}{\mathcal{P}}=\operatorname{min}_{i}\operatorname{deg}v_{i}$
and the Stanley depth of $I/J$ given by
$\operatorname{sdepth}_{S}I/J=\operatorname{max}_{\mathcal{P}}\operatorname{sdepth}{\mathcal{P}}$,
where ${\mathcal{P}}$ runs over the set of all partitions of $P_{I\setminus
J}$ (see [1], [8]). Stanley’s Conjecture says that
$\operatorname{sdepth}_{S}I/J\geq\operatorname{depth}_{S}I/J$.

Let $r$ be the number of squarefree monomials of degree $d$ of $I$ and $B$
(resp. $C$) be the set of squarefree monomials of degrees $d+1$ (resp. $d+2$)
of $I\setminus J$. Set $s=|B|$, $q=|C|$. If either $s>r+q$, or $r>q$, or
$s<2r$ then $\operatorname{sdepth}_{S}I/J\leq d+1$ and if Stanley’s Conjecture
holds then any of these numerical conditions would imply
$\operatorname{depth}_{S}I/J\leq d+1$, independently of the characteristic of
$K$. In particular this was proved directly in [4] and [7].

Suppose that $r=1$. If $d=1$ we showed in [5, Theorem 1.10] that almost always
Stanley’s Conjecture holds. It is the purpose of this note to complete the
result for $d\geq 1$ in the next form.

Theorem Suppose that $I\subset S$ is minimally generated by a squarefree
monomial $f$ of degree $d$, and a set $E$ of squarefree monomials of degrees
$\geq d+1$. Assume that $s\not=q+1$ and $\operatorname{sdepth}_{S}I/J=d+1$.
Then $\operatorname{depth}_{S}I/J\leq d+1$.

##  1\. Proof of the Theorem

We may assume that $s<q+1$ because if $s>q+1$ then by [4] we get
$\operatorname{depth}_{S}I/J\leq d+1$. Also we may suppose that
$C\subset(f,B)$ by [5, Lemma 1.6]. Induct on $|E|$. Suppose that
$E=\emptyset$. If $C=\emptyset$, then $\operatorname{depth}_{S}I/J\leq d+1$ by
[5, Lemma 1.5]. Otherwise, let $c=fx_{n-1}x_{n}\in C$ and
$I^{\prime}=(B\setminus\\{fx_{n-1},fx_{n}\\})$. In the exact sequence

$0\rightarrow I^{\prime}/J\cap I^{\prime}\rightarrow I/J\rightarrow
I/J+I^{\prime}\rightarrow 0$

the last term has sdepth $d+2$ since $c\not\in I^{\prime}+J$ and so the first
one has sdepth $\leq d+1$ by [6, Lemma 2.2] and even depth $\leq d+1$ by [3,
Theorem 4.3]. Then the Depth Lemma gives $\operatorname{depth}_{S}I/J\leq
d+1$.

Set $I_{n}=(B\setminus\\{fx_{n}\\}),J_{n}=I_{n}\cap J$. In the following exact
sequence

$0\rightarrow I_{n}/J_{n}\rightarrow I/J\rightarrow I/(I_{n}+J)\rightarrow 0$

the last term has sdepth depth $d+1$ since $[f,fx_{n}]$ is the whole poset of
$(f)/(f)\cap(I_{n}+J)$ and $x_{n}\not\in((J+I_{n}):f)$. If the first term has
sdepth $=d+1$ then by [[3], Theorem 4.3.] we get depth $=d+1$ and applying
Depth Lemma the conclusion follows. So we can assume that there exists a
partition ${\mathcal{P}}_{n}$ of $I_{n}/J_{n}$ with sdepth $d+2$. We may
suppose that all intervals of ${\mathcal{P}}_{b_{i}}$ (as well as of other
partitions which we will use) starting with a monomial $v$ of degree $\geq
d+2$ have the form $[v,v]$. In ${\mathcal{P}}_{n}$ we can’t have the interval
$[c,c]$, $c=fx_{n-1}x_{n}$, or the interval $[fx_{n-1},c]$ because otherwise
we can switch it with $[f,c]$ and get a partition of $I/J$ with sdepth $d+2$.
Thus we have in ${\mathcal{P}}_{n}$ the interval $[b_{1},c]$, $b_{1}\in E$.
Switching the interval $[b_{1},c]$ with the interval $[fx_{n},c]$ we get a
partition $P_{B_{b_{1}}}$ for $(B_{b_{1}})/J_{b_{1}}$ where
$B_{b_{1}}=B\setminus\\{b_{1}\\}$ and $J_{b_{1}}=(B_{b_{1}})\cap J$.

In ${\mathcal{P}}_{B_{b_{1}}}$ we have an interval $[\bar{c},\bar{c}]$ because
$s<q+1$. Thus there exists $b_{2}\in E$ such that $\bar{c}\in(b_{2})$. Note
that $\bar{c}\notin(b_{1})$ because otherwise we may replace in
${\mathcal{P}}_{B_{b_{1}}}$ the interval $[\bar{c},\bar{c}]$ with the interval
$[b_{1},\bar{c}]$ and get a partition ${\mathcal{P}}_{B}$ for $(B)/(B)\cap J$
with sdepth $=d+2$. This leads to a contradiction because we may change in
$P_{B}$ two intervals like $[fx_{i},fx_{i}x_{j}]$, $[fx_{j},c^{\prime}]$ for
some $c^{\prime}$ with $[f,fx_{i}x_{j}]$, $[c^{\prime},c^{\prime}]$ and get a
partition ${\mathcal{P}}$ for $I/J$ with sdepth $d+2$.

Let $I_{b_{2}}=(f,E\setminus\\{b_{2}\\})$, $J_{b_{2}}=I_{b_{2}}\cap J$. In the
following exact sequence

$0\rightarrow I_{b_{2}}/J_{b_{2}}\rightarrow I/J\rightarrow
I/(I_{b_{2}}+J)\rightarrow 0$

the last term has depth $\geq d+1$ because it is isomorphic with
$(b_{2})/(b_{2})\cap(I_{b_{2}}+J)$. If
$\operatorname{sdepth}I_{b_{2}}/J_{b_{2}}\leq d+1$ then the first term has
depth $\leq d+1$ by the induction hypothesis, so by the Depth Lemma we get
$\operatorname{depth}I/J\leq d+1$.

Now assume that $\operatorname{sdepth}I_{b_{2}}/J_{b_{2}}\geq d+2$ and let
$P_{b_{2}}$ be a partition on $I_{b_{2}}/J_{b_{2}}$ with sdepth $d+2$. In
${\mathcal{P}}_{b_{2}}$ we have the interval
$[f,fx_{i}x_{j}],i,j\in[n]\setminus\mbox{supp}f$. We have in
${\mathcal{P}}_{b_{2}}$ for all $b\in B\setminus\\{b_{2},fx_{i},fx_{j}\\}$ an
interval $[b,c_{b}]$. We define $h_{2}:(B\setminus\\{b_{2}\\})\rightarrow C$
by $b\rightarrow c_{b}$ and $h_{2}(fx_{i})=h_{2}(fx_{j})=fx_{i}x_{j}$ and let
$g_{2}:\operatorname{Im}h_{2}\rightarrow(B\setminus\\{b_{2}\\})$ defined by
$c_{b}\rightarrow b$, $g_{2}(fx_{i}x_{j})=fx_{i}$. Similarly we define
$h_{1},g_{1}$ for ${\mathcal{P}}_{B_{b_{1}}}$, that is $h_{1}$ is given by
$b^{\prime}\rightarrow c^{\prime}$ if ${\mathcal{P}}_{B_{b_{1}}}$ has the
interval $[b^{\prime},c^{\prime}]$.

We want to show that we can build a partition ${\mathcal{P}}$ with sdepth
$=d+2$ for $I/J$. Consider $a_{0}=b_{1}$ and
$c_{i-1}=h_{2}(a_{i-1}),a_{i}=g_{1}(c_{i-1}),i>0$. The construction stops at
step $e$ if

1) $a_{e}=b_{2}$,

2) $c_{e}\notin\operatorname{Im}h_{1}$,

3)$a_{e}=fx_{j}$ after $a_{u}=fx_{i},u<e$ already appeared. Note that here we
have fixed $a_{u}=fx_{i}$.

In the first case we set $c_{e}=\bar{c}$ and we see that $h_{1}$ gives a
bijection between $\\{a_{1},\ldots,a_{e}\\}$ and $\\{c_{0},\ldots,c_{e-1}\\}$.
But $h_{1}$ also gives a bijection between
$B\setminus\\{b_{1},a_{1},\ldots,a_{e}\\}$ and
$C\setminus\\{\bar{c},c_{0},\ldots,c_{e-1}\\}$. Then the intervals
$[a_{p},c_{p}]$, $0\leq p\leq e$ and the intervals
$[g_{1}({\tilde{c}}),{\tilde{c}}]$, ${\tilde{c}}\in
C\setminus\\{\bar{c},c_{0},\ldots,c_{e-1}\\}$ and some other intervals
starting with monomials of degree $\geq d+2$ give a partition
${\mathcal{P}}_{B}$ of $P_{B/B\cap J}$ with sdepth $\geq d+2$. As before this
is a contradiction with sdepth $I/J=d+1$.

In the second case, as above we see that the intervals $[a_{p},c_{p}]$, $0\leq
p\leq e$ and the intervals $[g_{1}({\tilde{c}}),{\tilde{c}}]$, ${\tilde{c}}\in
C\setminus\\{\bar{c},c_{0},\ldots,c_{e-1}\\}$ and some other intervals
starting with monomials of degree $\geq d+2$ give a partition
${\mathcal{P}}_{B}$ of $P_{B/B\cap J}$ with sdepth $\geq d+2$. Contradiction.

In the last case we see as usual, that $h_{1}$ gives a bijection between
$\\{a_{1},\ldots,a_{e}\\}$ and $\\{c_{0},\ldots,c_{e-1}\\}$. But $h_{1}$ also
gives a bijection between $B\setminus\\{b_{1},a_{1},\ldots,a_{e}\\}$ and
$C\setminus\\{c_{0},\ldots,c_{e-1}\\}$. Then the intervals $[a_{p},c_{p}]$,
$0\leq p\leq e-1,p\neq u$ and the intervals
$[f,c_{u}],[g_{1}({\tilde{c}}),{\tilde{c}}]$, ${\tilde{c}}\in
C\setminus\\{c_{0},\ldots,c_{e-1}\\}$ and some other intervals starting with
monomials of degree $\geq d+2$ give the partition ${\mathcal{P}}$ of $P_{I/J}$
with sdepth $\geq d+2$. Contradiction.

######  Example 1.1.

Let $n=5$, $I=(x_{1}x_{2},x_{3}x_{4}x_{5})$ and
$J=(x_{1}x_{2}x_{3}x_{5},x_{1}x_{2}x_{4}x_{5})$. We see that we have
$\operatorname{sdepth}I/J=d+1=3$ and
$B=\\{x_{1}x_{2}x_{3},x_{1}x_{2}x_{4},x_{1}x_{2}x_{5},x_{3}x_{4}x_{5}\\}$ and
$C=\\{x_{1}x_{2}x_{3}x_{4},x_{1}x_{3}x_{4}x_{5},x_{2}x_{3}x_{4}x_{5}\\}$ so we
are in the case $s=q+1$. We can get $\operatorname{depth}I/J\leq 3$ by using
[5, Lemma 1.5] for $u=x_{1}x_{2}x_{5}$.

######  Remark 1.2.

If in the above example change just one monomial from the generators of $J$,
namely take $J=(x_{1}x_{2}x_{4}x_{5},x_{2}x_{3}x_{4}x_{5})$ then we have
$\operatorname{sdepth}_{S}I/J=4$ because the partition induced by the
intervals $[x_{1}x_{2},x_{1}x_{2}x_{3}x_{4}]$,
$[x_{3}x_{4}x_{5},x_{1}x_{3}x_{4}x_{5}]$,
$[x_{1}x_{2}x_{5},x_{1}x_{2}x_{3}x_{5}]$ has sdepth $d+2=4$. Also we have
$\operatorname{depth}_{S}I/J=4$.

A question is hinted by the following example.

######  Example 1.3.

Let $n=5$, $I=(x_{1},x_{2}x_{3},x_{2}x_{4},x_{2}x_{5},x_{3}x_{4})$ and $J$ the
ideal generated by all squarefree monomials of $I$ of degrees $4$. Then
$E=\\{x_{2}x_{3},x_{2}x_{4},x_{2}x_{5},x_{3}x_{4}\\}$, $f=x_{1}$,
$B=\\{x_{1}x_{2},x_{1}x_{3},x_{1}x_{4},x_{1}x_{5},E\\}$,
$C=\\{x_{1}x_{2}x_{3},x_{1}x_{2}x_{4},x_{1}x_{2}x_{5},x_{1}x_{3}x_{4},$
$x_{2}x_{3}x_{4},x_{2}x_{3}x_{5},x_{2}x_{4}x_{5}\\}$. Thus $s=8=q+1$. We see
that $\operatorname{sdepth}_{S}I/J=d+2=3$ but
$\operatorname{depth}_{S}I/J=d+1=2$. Note that here

$C\subset(\cup_{a\in E}C\cap(f)\cap(a))\cup(\cup_{a,a^{\prime}\in
E,a\not=a^{\prime}}C\cap(a)\cap(a^{\prime}),$

a condition which might imply always $\operatorname{depth}_{S}I/J\leq d+1$,
the inequality being not true for sdepth.

## References

  * [1] J. Herzog, M. Vladoiu, X. Zheng, How to compute the Stanley depth of a monomial ideal, J. Algebra, 322 (2009), 3151-3169.
  * [2] D. Popescu, Depth and minimal number of generators of square free monomial ideals, An. St. Univ. Ovidius, Constanta, 19 (2), (2011), 187-194.
  * [3] D. Popescu, Depth of factors of square free monomial ideals, to appear in Proceedings AMS, arXiv:AC/1110.1963.
  * [4] D. Popescu, Upper bounds of depth of monomial ideals, to appear in J. Commutative Alg., (2012),arXiv:AC/1206.3977.
  * [5] D. Popescu, A. Zarojanu, Depth of some square free monomial ideals, Bull. Math. Soc. Sci. Math. Roumanie, 56(104), 2013,117-124.
  * [6] A. Rauf, Depth and Stanley depth of multigraded modules, Comm. Algebra, 38 (2010),773-784.
  * [7] Y.H. Shen, Lexsegment ideals of Hilbert depth 1, (2012), arxiv:AC/1208.1822v1.
  * [8] R. P. Stanley, Linear Diophantine equations and local cohomology, Invent. Math. 68 (1982) 175-193.