text:
## Measuring coaxial cable loss by reflection with a VNA

At Measuring coaxial cable loss with a voltmeter I discussed measuring terminated coax cable loss with an RF voltmeter, and it had some real practical limitations.

This article explores using a nanoVNA to measure line loss in a similar scenario. We will use 6m of Belden 8359 (RG58A/U) @ 3.6MHz.

The same technique could be used with a quality antenna analyser.

## Expectation

A short digression, what is the specification Matched Line Loss (MLL) at 3.6MHz? Using TLLC we get 0.171dB, that is our expectation.

## Return Loss of SC section

A common method proposed is to measure Return Loss (RL) of a section with load end RL=0dB and halve it. Many experts advise that the section should be terminated in a short circuit (S) because short circuits are more reliable than open circuits. So let’s get cracking.

Above is measured |s11| using a nanoVNA with recent OSL calibration from 1-30MHz. |s11| @ 3.6MHz is by eye -0.651dB, RL=-|S11|, so RL/2=0.651/2=0.325dB. Continue reading Measuring coaxial cable loss by reflection with a VNA

## Measuring coaxial cable loss by transmission measurement with a directional wattmeter

The article Measuring coaxial cable loss with a voltmeter discussed some pitfalls of that measurement method, starting with the influence of theoretical error in actual Zo at lower frequencies.

You might expect that using a directional wattmeter has exactly the same problems because as many online experts advise, at the end of the day they are just a voltmeter.

They are wrong, a Bird 43 might use a half wave detector driving a d’Arsonval meter and you might regard that to be a voltmeter, but the RF signal it measures is a combination of samples of forward and reflected waves wrt to its calibration impedance (usually 50+j0Ω) and we will see that makes a difference.

Where a directional wattmeter is calibrated for a purely real impedance (ie X=0), then the relationship $$P=P_{fwd}-P_{ref}$$ holds true (On the concept of that P=Pfwd-Prev).

Lets take an example to explore the theoretical answer. We will use 10m of Belden 8359 (RG58A/U) @ 3.6MHz.

Lets model the scenario in TLLC. We will select the “Use Lint” switch for a better model of this specific cable at 3.6MHz and take the “Long” output.

## Measuring coaxial cable loss with a voltmeter

A question asked online about measuring terminated coax cable loss with an RF voltmeter and whether to condemn it based on comparison with specs raises an interesting case to discuss.

The subject raises some immediate concerns:

• the accuracy of the termination;
• the accuracy of the voltmeter;
• the extent to which the voltmeter disturbs the thing being measured; and

Lets take an example to explore the theoretical answer. We will use 10m of Belden 8359 (RG58A/U) @ 3.6MHz.

Lets model the scenario in TLLC. We will select the “Use Lint” switch for a better model of this specific cable at 3.6MHz and take the “Long” output.

Above is the input form. Continue reading Measuring coaxial cable loss with a voltmeter

## Chinese wattmeter / power analyser fix

I bought a little wattmeter / power analyser with SB50 style plugs on it on eBay for about \$20.

These devices have been common in the RC market for many years, and I have found them useful for a number of things but note that the input -ve lead is NOT directly connected to the output -ve lead, you cannot use them where the input -ve and output -ve are common.

## The problems

Above is the promo pic. Of course they are not Anderson plugs, but clones. Continue reading Chinese wattmeter / power analyser fix

## Simsmith bimetal line type

This article discusses various measurements and models of Wireman 551 windowed ladder line, including adapting Simsmith’s bimetal line type to bear on the problem.

## Measurements

A starting point for characterising the matched line loss (MLL) of the very popular Wireman 551 (W551) windowed ladder line is the extrapolation of measurements by (Stewart 1999) to 1.8MHz. Since the measurements were made at and above 50MHz where the W551 has copper like performance, this is likely to underestimate actual MLL and such wide extrapolation introduces its own uncertainty. Nevertheless, the datapoint is MLL=0.00227dB/m.

Dan Maquire recently posted a chart summarising measurements of these lines.

For the purposes of this article, let’s tabulate the MLL at 1.8MHz in dB/m. Continue reading Simsmith bimetal line type

## Stub matching loss can bite you

An article by K2PO in QST Feb 2020 entitled An SWR shifting T illustrates the pitfalls in naive design and implementation of transmission line matching systems. I say naive because the article does not address the matter of loss, yet QST publishes it as an example. Continue reading Stub matching loss can bite you

## A thinking exercise on Jacobi Maximum Power Transfer #4

The article A thinking exercise on Jacobi Maximum Power Transfer #3 discussed Kurokawa’s power reflection coefficient as in indicator of mismatch at a system node.

Above is a demonstration circuit in Simsmith, a linear source with Thevenin equivalent impedance of 50-j5Ω. The equivalent voltage is specified by useZo, which like much of Simsmith is counter intuitive (as you are not actually directly specifying generator impedance):

Vthev and Zthev are chosen so that ‘useZo’ will deliver 1 watt to a circuit impedance that equals the G.Zo. Zthev will be Zo*.

## The transmitter matching problem

In the article The system wide conjugate match stuff crashes out again I worked through an example proffered in an online discussion to show that Walter Maxwell’s teachings on system wide simultaneous conjugate match do not tend to occur in practical systems.

## Why are hams so obsessed with conjugate matching?

The answer is on the face of it quite simple. Continue reading The transmitter matching problem

## Strength of reinforcement of nanoVNA-H connectors

The nanoVNA-H connectors are end launch PCB connectors and they have a decidedly spongy feel as 1Nm torque is approached. This was due to flexing of the PCB and was likely to lead to track cracks in the longer term.

Specs for SMA connectors range from minimum of 0.2Nm torque to maximum of 1.7Nm, but 0.6Nm and 1.0Nm are common commercial practice.

Some nanoVNA sellers state:

As the SMA ports are made of cast copper, please not connect hard 50-7 / RG213 and other cables directly to the SMA ports through M-to-SMA connector to avoid damaging the SMA ports. You can use the included SMA cable to connect to the SMA port as shown in the picture below, and then use M to SMA connector.

Clearly Chinese Cheats, they will say anything to make a sale and anything to avoid commitment to quality. These connectors are very unlikely to be copper, but are likely to be a copper alloy: brass. What they also avoid in the above statement is claim for PCB damage due to flexure of the SMA connectors torqued to accepted industry torque for reliable connections and measurement.

Above is a pic of a modification to reinforce the connectors. This article sets out the analysis of just the solder joint within the cross section of the brass pieces.

A side effect is that this modification bonds the ground planes for the input and output parts of the nanoVNA via the brass bar where they have been kept isolated to some extent.

I should note that there has been much discussion online as to whether the noise floor of the nanoVNA is degraded by the shields fitted to the board, and various modifications to the shields. Some of this discussion proposes that the issue is mostly around the mixers and noise loops, and I note that in -H designs prior to v3.3, the mixer power supply was not adequately decoupled. It is possible that electrical connection of the SMA connectors in this way degrades noise performance at some frequencies. No significant change was observed in the noise floor of s11 or s21 channels from 1 to 300MHz (I don’t regard instrument performance to be good above 300MHz). I have not seen credible evidence of degradation of the nanoVNA-H v3.3 build.

If indeed bonding the two SMA connectors close to the instrument increases the noise floor or has other performance impacts as suggested, it questions whether the currents on the exterior of the coax influence measurement (which it should not) and it questions whether two port measurement fixtures or adapters should  be attached close to the nanovna.

At first, the strength of the butt soldered joint might seem a simple case of beam analysis where the beam is of cast solder of the same cross section l x w as the soldered joint. Continue reading Strength of reinforcement of nanoVNA-H connectors

## nanoVNA-H – recovery

I often see reports that a nanoVNA has been ‘bricked’. The term seems to have become part of the vernacular of would be pros. The term ‘bricked’ certainly applies to electronics that can no longer be programmed through ‘ordinary means’ and is to all intents and purposes as useful as brick, but in most cases, the nanoVNA is recoverable.

The STM32F072 chip  used on the original nanoVNA has some features that make the firmware update process simple and robust, and difficult to mess up.

The normal way of doing a firmware update is using the DFU protocol from a PC over the USB interface. To use this, the device has to be “put into DFU mode”, this means that the chip is reset and started executing the bootloader in permanent system memory.

The concept of DFU is that normal client programs used with the device can easily be extended to include the DFU function as just another menu function of the client software. I am not aware of any nanoVNA client that does this.

So, you need to use a programming client, and for Windows a good choice is ST’s DfuSeDemo. You may need to convert the distributed file format using Dfu file manager from the same distribution, not all developers distribute a .dfu file.

There is a pin on the board, BOOT0, that must be held high during reset to enter the on-chip bootloader. Later firmware versions also provide a menu option to enter the bootloader, but if an attempted upgrade messes up the menu, you may need to use the BOOT0 pin bridged to the adjacent VDD pin while you power cycle the nanovna.

Above is the rear view of the board, and a jumper using pogo pins to bridge BOOT0 to VDD. Continue reading nanoVNA-H – recovery


text:
# Math Help - [SOLVED] Polynomial question

1. ## [SOLVED] Polynomial question

Hi, this is probably quite a simple question, but i am stuck, and can't find anything like it in the lecture notes, so your help will be appreciated.

the question is
Write down the polynomial P in x,y such that that x^4 - x^4 = (x-y)P

Explanations with answers will really help me too! Thanks

2. Originally Posted by Rapid_W
Hi, this is probably quite a simple question, but i am stuck, and can't find anything like it in the lecture notes, so your help will be appreciated.

the question is
Write down the polynomial P in x,y such that that x^4 - x^4 = (x-y)P

Explanations with answers will really help me too! Thanks
x^4-x^4 = 0 . Sure you didn't mean x^4-y^4?

If so x^4-y^4 is the difference of two squares:

$x^4-y^4 = (x^2-y^2)(x^2+y^2)$

However, x^2-y^2 is also the difference of two squares

$x^4-y^4 = (x-y)(x+y)(x^2+y^2)$

which gives $P = (x+y)(x^2+y^2) = x^3 + xy^2 + x^2y + y^3$

3. Yes, i did mean that sorry! Thanks very much for the answer

format: plain


text:
poita.org

# The Condenser Part 1

Last night I rewatched Joe Armstrong’s excellent keynote from this year’s Strange Loop conference. He begins the talk with a fairly standard, but humorous lament about the sorry state of software, then goes on to relate this to some physical quantities and limits. He finishes by suggesting some possible directions we can look to improve things.

One of his suggestions is to build something called “The Condenser”, which is a program that takes all programs in the world, and condenses them down in such a way that all redundancy is removed. He breaks this task down into two parts:

He also explains the obvious, and easy way to do Part 1.

At this point I remembered that I hadn’t written a lot of D recently, and although Joe is talking about condensing all files in the world, I was kind of curious how much duplication there was just on my laptop. How many precious bytes am I wasting?

It turns out that The Condenser Part 1 is very easy to write in D, and even quite elegant.

import std.algorithm;
import std.digest.sha;
import std.file;
import std.parallelism;
import std.stdio;
import std.typecons;

auto process(DirEntry e) {
ubyte[4 << 10] buf = void;  // 4kb buffer, uninitialized
auto sha1 = File(e.name).byChunk(buf[]).digest!SHA1;
return tuple(e.name, sha1, e.size);
}

void main(string[] args) {
string[ubyte[20]] hash2file;  // hash table of SHA1 -> filename
auto files = dirEntries(args[1], SpanMode.depth, false)
.filter!(e => e.isFile);
if (string* original = t[1] in hash2file) {
writefln("%s %s duplicates %s", t[2], t[0], *original);
} else {
hash2file[t[1]] = t[0];
}
}
}

I’ll explain the code a little, starting from main. The files variable uses dirEntries and filter to produce a list of files (the filter is necessary since dirEntries also returns directories). dirEntries is a lazy range, so the directories are only iterated as necessary. Similarly, filter creates another lazy range, which removes non-file entries.

The foreach loop corresponds to Joe’s do loop. While I could have just iterated over files directly, I instead iterate over a taskPool.map, a semi-lazy map from David Simcha’s std.parallelism that does the processing in parallel on multiple threads. It is semi-lazy because it eagerly takes a chunk of elements at a time from the front of the range, processes them in parallel, then returns them back to the caller to consume. The task pool size defaults to the number of CPU cores on your machine, but this can be configured.

The process function is where the hashing is done. It takes a DirEntry, allocates an uninitialized (= void) 4kb buffer on the stack and uses that buffer to read the file 4kb at a time and build up the SHA1. Again, byChunk returns a lazy range, and digest!SHA1 consumes it. Lazy ranges are very common in idiomatic D, especially in these kinds of stream processing type applications. It’s worth getting familiar with the common ranges in std.algorithm and std.range.

I ran the program over my laptop’s home directory. Since the duplicate file sizes are all in the first column, I can just use awk to sum them up and find the total waste:

$sudo ./the-condenser . | awk '{s+=$1} END {print s}'
2347353793

That’s 2.18Gb of duplicate files, which is around 10% of my home dir.

In some cases the duplicates are just files that I have absentmindedly downloaded twice. In other cases it’s duplicate music that I have both in iTunes and Google Play. For some reason, the game Left 4 Dead 2 seems to have a lot of duplicate audio files.

So, in theory, I could save 10% by deduplicating all these files, but it’s not a massive amount of waste. It doesn’t seem worth the effort trying to fix this. Perhaps it would be nice for the OS or file system to solve this automatically, but the implementation would be tricky, and still maybe not worth it.

Part 2 of the Condenser is to merge all similar files using least compression difference. This is decidedly more difficult, since it relies on near-perfect compression, which is apparently an AI-hard problem. Unfortunately, solving AI is out of scope for this post, so I’ll leave that for another time :-)

# Cube Vertex Numbering

If you do any sort of graphics, physics, or 3D programming in general then at some point you are going to be working with cubes, and at some point you are going to need to assign a number to each vertex in those cubes. Usually this is because you need to store them in an array, or maybe you are labelling the children of an octree, but often you just need some consistent way of identifying vertices.

For whatever reason, a surprisingly common way of numbering vertices is like this, with the bottom vertices numbered in counter-clockwise order followed by the top vertices in counter-clockwise order (warning, incoming ASCII art):

        7-------6
/|      /|
4-+-----5 |
| |     | |   y
| 3-----+-2   | z
|/      |/    |/
0-------1     +--x

Depending on what you are doing, there’s generally only a few applications of the numbering system:

• Converting a number to a coordinate.
• Converting a coordinate to a number.

Unfortunately, this common numbering scheme makes none of these tasks easy, and you have no choice but to produce tables of coordinates and adjacency lists for each vertex number. This is tedious, error-prone, and completely unnecessary.

Here is a better scheme:

        3-------7
/|      /|
2-+-----6 |
| |     | |   y
| 1-----+-5   | z
|/      |/    |/
0-------4     +--x

This numbering uses the Lexicographic Ordering of the vertices, with 0 being the lexicographically first vertex, and 7 being the last.

Number
(decimal)
Number
(binary)
Coordinate
00000, 0, 0
10010, 0, 1
20100, 1, 0
30110, 1, 1
41001, 0, 0
51011, 0, 1
61101, 1, 0
71111, 1, 1

I’ve included the binary representation of the vertex number in table above, because it illuminates the key property of this scheme: the coordinate of a vertex is equal to the binary representation its vertex number.

\begin{aligned} coordinate(n) &= ((n \gg 2) \mathrel{\&} 1, (n \gg 1) \mathrel{\&} 1, (n \gg 0) \mathrel{\&} 1) \\ number(x, y, z) &= (x \ll 2) \mathrel{|} (y \ll 1) \mathrel{|} (z \ll 0) \end{aligned}

(Of course, the zero shifts are unnecessary, but I’ve added them to highlight the symmetry.)

This numbering scheme also makes adjacent vertex enumeration easy. As an adjacent vertex is just a vertex that differs along one axis, we just need to flip each bit using XOR to get the adjacent vertices:

\begin{aligned} adj_x(n) &= n \oplus 100_2 \\ adj_y(n) &= n \oplus 010_2 \\ adj_z(n) &= n \oplus 001_2 \end{aligned}

It should be clear that this numbering scheme trivially extends into higher dimension hypercubes by simply using more bits in the representation, and extending the formulae in obvious ways.

So there you have it. Whenever you are looking to number things and aren’t sure what order to use, start with lexicographic. It usually has nice encoding and enumeration properties, and if not then it is probably no worse than any other ordering.

# Range-Based Graph Search in D

I’ve just made my first commit of a range-based graph library for D. At the moment it only contains a few basic search algorithms (DFS, BFS, Dijsktra, and A*), but I wanted to write a bit about the design of the library, and how you can use it.

As a bit of a teaser, the snippet below shows how you can use the library to solve those word change puzzles (you know, the ones when you have to get from one word to another by only changing one letter at a time?)

string[] words = File("/usr/share/dict/words")
.byLine
.filter!(w => w.length == 5)
.map!"a.idup"
.array();
enum string start = "hello";
enum string end = "world";
static d(string a, string b) { return zip(a, b).count!"a[0] != a[1]"; }
auto graph = implicitGraph!(string, u => words.filter!(v => d(u, v) == 1));
graph.aStarSearch!(v => d(v, end))(start).find(end).path.writeln();

This promptly produces the desired result:

["hello", "hollo", "holly", "molly", "mouly", "mould", "would", "world"]

The last two lines are the interesting part. The first of those lines defines our graph as an implicit graph of words connected by one-letter changes. The second line performs the A* search and writes the resultant path to stdout.

On the second-last line, graph is defined as an implicitGraph. An implicit graph is a graph that is represented by functions rather than in-memory data structures. Instead of having an array of adjacency lists, we just define a function that returns a range of adjacent words (that’s the second parameter to implicitGraph). This representation saves us the tedium of generating the graph beforehand, and saves your RAM from having to store it unnecessarily. It also makes for succinct graph definitions!

The last line is where the algorithm is called. Unlike most other graph libraries, stdex.graph implements graph searches as ranges – iterations of the graph vertices. aStarSearch returns a range of vertices in the order they would be visited by the A* search algorithm (parameterized by the A* heuristic). By implementing the search as a range, the user can take advantage of Phobos’ multitude of range algorithms.

For instance, suppose you want to count the number of nodes searched by the algorithm until it reaches the target node. For this task, you can just use countUntil from std.algorithm.

auto search = graph.aStarSearch!(v => d(v, end))(start);
writefln("%d nodes visited", search.countUntil(end));

For tuning and debugging, it might be useful to print out the nodes visited by the algorithm as it runs.

foreach (node; search.until(end))
writeln(node);

When no path is available, graph search algorithms typically end up searching the entire vertex space. It is common to cut-off the search after a certain threshold of nodes have been searched. This can be accomplished by takeing only so many nodes from the search.

auto result = search.take(50).find(end);
if (result.empty)
writeln("Not found within 50 nodes");

Similarly, you could have the search continue until 10 seconds have elapsed.

alias now = TickDuration.currSystemTick;
auto t = now;
auto result = search.until!(_ => (now - t).seconds > 10).find(end);
if (result.empty)
writeln("Not found in 10 seconds");

The beauty of all this is that none of these features are part of the graph library – they come for free as a side-effect of being a range.

One unsolved part of the design for the graph searches is how to handle visitation. The Boost Graph Library solves this by having users implement a visitor object, which has to define a suite of callback methods, one for each event (vertex discovered, examine edge, etc.) This is certainly mimicable in D, but it may be more effective to model visitation with output ranges, which would again allow composition with existing Phobos constructs. This is what I will be investigating next.

# Ranges Part 1 - Basics

Iteration is one of the most common activities in programming. Few programming tasks can be accomplished without looping or recursing over some set of values, whether it be a stream of bytes from a file, elements of an array, rows in a database, or nodes in an implicitly generated graph. Programs need to iterate, and programming languages need to provide idioms for iteration.

In D, iteration is achieved through the use of ranges. Broadly speaking, a range defines a sequence of values. There are many styles of ranges. For example, some ranges lazily generate their values instead of iterating over data; some ranges are infinite; some ranges can be iterated from both ends; and some ranges allow you to jump around to any index (like arrays). For the most part, the details of how a particular range operates is up to the range implementor.

So how do you implement a range? At the most basic level, a range is just a type with three member functions: front, empty, and popFront.

• front returns the value from the front of the range.
• empty returns true if the range has been exhausted.
• popFront removes the first value from the range.

As a simple example, here is a range that counts from 0 to ‘n’.

struct Iota
{
private int m_current = 0;
private int m_target;

this(int n) { m_target = n; }
@property int front() { return m_current; }
@property bool empty() { return m_current == m_target; }
void popFront() { m_current++; }
}

(The name Iota is a Greek letter. In a tradition started by the programming language APL, it is used to represent consecutive integers in several languages)

Notice that there is no need to inherit from any sort of IRange interface. There’s nothing magic about ranges, they are just simple types with those functions defined.

To iterate over a range, you can manually call those functions using a for loop, or use the built-in foreach loop in D, which knows about ranges.

void main()
{
import std.stdio;
foreach (x; Iota(10))
writeln(x);
}

As expected, this will print out the numbers 0 through 9, one per line. Of course, writeln knows about ranges too, so writeln(Iota(10)) works as well, and will print out [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], formatted like an array.

Writing functions that work with ranges is not difficult. Suppose we want to write a function to count the number of elements in a range. This can be achieved by accepting the range as a template parameter and iterating the range using popFront() explicitly, like so:

size_t count(Range)(Range r)
{
size_t n = 0;
while (!r.empty)
{
++n;
r.popFront();
}
return n;
}

unittest
{
assert(count(Iota(10)) == 10);
}

By using templates, we can create range types that are templated on other range types. For example, consider a skip range that skips every second element in another range. You could define it like this:

struct Skip(Range)
{
private Range m_range;

this(Range r) { m_range = r; }

// front and empty just forward to the sub-range.
@property auto ref front() { return m_range.front; }
@property bool empty() { return m_range.empty; }

// popFront also forwards to the sub-range, but pops off two
// elements at a time, instead of one.
void popFront()
{
m_range.popFront();
if (!m_range.empty)
m_range.popFront();
}
}

We can then use Skip in conjunction with Iota to skip through consecutive integers.

void main()
{
import std.stdio;
writeln(Skip!Iota(Iota(10))); // [0, 2, 4, 6, 8]
}

Notice that we have to redundantly specify Iota as a template parameter to Skip. This is because D doesn’t currently support type inference for template type constructors. A common workaround is to create a module-level function that wraps the constructor:

auto skip(Range)(Range r) { return Skip!Range(r); }
auto iota(int n) { return Iota(n); }

We can then use these like so:

writeln(iota(10).skip());

The above code also makes use of another D feature: uniform function call syntax, which basically means f(x) can be written as x.f() as if f were a member function of x. If you come from the C# world, you can kind of think of it as every free function being an Extension Method. We could have also written 10.iota().skip() or just plain skip(iota(10)). There’s no difference, so choose whatever you think is most readable.

The ability to combine arbitrary ranges is perhaps their most powerful feature. There’s no reason we need to stop at combining just two ranges:

writeln(iota(10)); // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
writeln(iota(10).skip()); // [0, 2, 4, 6, 8];
writeln(iota(10).skip().skip()); // [0, 4, 8];
writeln(iota(10).skip().skip().skip()); // [0, 8];

It shouldn’t be hard to imagine the kind of flexibility and expressiveness that can be achieved once you have a large vocabulary of ranges at your disposal.

In Part 2 we’ll look at some of the different categories of ranges.

# DustMite - Code Minimizer

Yesterday I discovered DustMite, a source code minimizer tool for D.

What’s a source code minimizer? It’s a program that takes some source code, and automatically removes lines, or even whole files from the source while maintaining some invariant (e.g. it still builds, or still gives a particular output). The usual use case is to produce a minimal reproduction test case for a bug, which is exactly what I used it for.

I had a problem in a medium-sized D project where anytime I had some sort of compile-time error, such as a typo in a variable name, DMD (the D compiler), would spew out pages and pages of false errors, triggered by some other module in my codebase. The errors were completely irrelevant. This was quite annoying because it made it difficult to see the actual error. So, like a good programmer, I decided to file a bug report.

Step one in filing a good bug report is to create a minimal test case. I tried to do this manually by pulling out what seemed to be the relevant parts of the code that would reproduce the error, but I couldn’t get it to happen. I could easily and consistently reproduce the bug in the full codebase, but the project is about 10,000 lines of code, so minimizing it manually from there would be very time consuming.

I’d heard about DustMite on the forums, so I thought I’d give it a go.

Installing was easy enough.

% git clone https://github.com/CyberShadow/DustMite.git
% cd DustMite
% dmd dustmite.d dsplit.d
% ln -s ~/DustMite/dustmite ~/bin

Next step was to prepare the project for minification. All you need to do is make a full copy of the codebase, and remove any unnecessary files (e.g. object files, data files – anything not needed for reproduction).

Next you need to devise a test command. This is a command that should return 0 if the bug is still present, and non-zero otherwise. For example, suppose we had this (trivial) program:

import std.stdio;
import std.string;

string world() { return "world!"; }

void main()
{
write(hello());
write(", ");
write(world());
write("\n");
}

I’ve got an obvious bug here in that hello() is undefined. Trying to compile this gives Error: undefined identifier hello. If we wanted to minimize this then we need a command, which, when run, will return 0.

Compiling and greping for the error would be perfect for this.

% dmd test.d 2>&1 | grep -q "undefined identifier hello"
% echo \$?
0

This runs the compiler (dmd test.d), redirects the error messages to stdout (2>&1) then pipes the result (|) to grep, which searches for that string without producing output (-q = quiet). grep returns 0 if it finds anything, and 1 otherwise.

The DustMite wiki provides a list of useful test scripts.

Finally, we just run DustMite with that test command.

% dustmite testdir 'dmd test.d 2>&1 | grep -q "undefined identifier
hello"'
None => Yes
############### ITERATION 0 ################
[  0.0%] Remove [] => No
[  1.6%] Remove [0] => No (cached)
[  3.3%] Remove [01] => No
...
[ 82.4%] Remove [000001] => No (cached)
[ 88.2%] Remove [000000] => No (cached)
[ 94.1%] Remove [0000000] => No (cached)
Done in 36 tests and 10 secs and 165 ms; reduced version is in
testdir.reduced

And checking testdir.reduced/test.d confirms that the source has been reduced.

% cd testdir.reduced
% cat test.d
void main()
{
hello;
}

For my project, DustMite took 8 minutes, and reduced roughly 10,000 lines of code down to about 10, and perfectly reproduced the issue. The problem I was having trying to reproduce manually was that the repro required that you pass the files in a specific order to the compiler, and it also required an extra file that seemingly has nothing to do with the issue. I don’t think I would have ever minimized it without DustMite.


text:
KMA Preprints in 2008

MATH-KMA-2008/256

 Miroslav Bulicek, Dalibor Prazak: A note on the dimension of the global attractor for abstract semilinear hyperbolic problem 6 pages, pdf file 95 kB
Published in Appl. Math. Lett. 22 (2009), no. 7, 1025-1028.
... and therefore removed from the preprint server. Mail to the author(s) for reprints.

MATH-KMA-2008/257

 Eva Fasangova, Pedro J. Miana: Hilbert, Dirichlet and Fejer families of operators arising from $C_{0}$-groups and cosine functions 24 pages, pdf file 288 kB
Published in Semigroup Forum 80 (2010), no. 1, 33–60.
... and therefore removed from the preprint server. Mail to the author(s) for reprints.

MATH-KMA-2008/258

 Josef Danecek, Oldrich John, Jana Stara: On the Holder continuity of gradient of solutions to a class of elliptic systems 11 pages, pdf file 200 kB
Published in Functiones et Approximatio 40.2 (2009), 155-164.
... and therefore removed from the preprint server. Mail to the author(s) for reprints.

MATH-KMA-2008/259

 Jakub Duda, Ludek Zajicek: Semiconvex functions: representations as suprema of smooth functions and extensions 19 pages, pdf file 245 kB
Published in J. Convex Anal. 16 (2009), 239-260.
... and therefore removed from the preprint server. Mail to the author(s) for reprints.

MATH-KMA-2008/260

 Jakub Duda, Ludek Zajicek: Curves in Banach spaces which allow a $C^{2}$ parametrization 22 pages, pdf file 330 kB
Published in J. Lond. Math. Soc. (2) 83 (2011), no. 3, 733–754.
... and therefore removed from the preprint server. Mail to the author(s) for reprints.

MATH-KMA-2008/261

 Vaclav Vlasak, Miroslav Zeleny: Compact sets of continuity for Borel functions 7 pages, pdf file 128 kB
Published in Topology Appl. 155 (2008), no. 15, 1672–1676.
... and therefore removed from the preprint server. Mail to the author(s) for reprints.

MATH-KMA-2008/262

 Ondrej Kalenda, Jiri Spurny: Boundaries of compact convex sets and fragmentability 20 pages, pdf file 258 kB
Published in J. Funct. Anal. 256 (2009), no. 3, 865-880.
... and therefore removed from the preprint server. Mail to the author(s) for reprints.

MATH-KMA-2008/263

 Ondrej Kurka, Dusan Pokorny: Porosity and the Darboux property of Frechet derivatives 12 pages, pdf file 194 kB
Published in Real Analysis Exchange 34(2) (2009), 319-332.
... and therefore removed from the preprint server. Mail to the author(s) for reprints.

MATH-KMA-2008/264

 Miroslav Kacena, Jiri Spurny: Affine images of compact convex sets and maximal measures 8 pages, pdf file 128 kB
Published in Bulletin des Sciences Mathematiques 133 (2009), 493-500.
... and therefore removed from the preprint server. Mail to the author(s) for reprints.

MATH-KMA-2008/265

 Miroslav Kacena: Products and projective limits of function spaces 26 pages, pdf file 291 kB
Published in Comment. Math. Univ. Carolin. 49,4 (2008) 547-578.
... and therefore removed from the preprint server. Mail to the author(s) for reprints.

MATH-KMA-2008/266

 Miroslav Bacak: Minimal measures and nonsimplicial function cones 5 pages, pdf file 144 kB
Submitted to (not intended for publication)

MATH-KMA-2008/267

 Miroslav Bacak, Petr Hajek: Mazur intersection property for Asplund spaces 6 pages, pdf file 172 kB
Published in J. Funct. Anal. 255 (2008), no. 8, 2090–2094.
... and therefore removed from the preprint server. Mail to the author(s) for reprints.

MATH-KMA-2008/268

 Stanislav Hencl: On the weak differentiability of $u \\circ f^{-1}$ 9 pages, pdf file 151 kB
Published in Math. Scand. 107 no.2 (2010), 198-208.
... and therefore removed from the preprint server. Mail to the author(s) for reprints.

MATH-KMA-2008/269

 Amiran Gogatishvili, Lubos Pick, Jan Schneider: The rearrangement-invariant hull of a Besov space 18 pages, pdf file 181 kB
Published in Rev. Mat. Complutense 25, 1 (2012), 267-283 .
... and therefore removed from the preprint server. Mail to the author(s) for reprints.

MATH-KMA-2008/270

 Ron Kerman, Lubos Pick: Explicit formulas for optimal rearrangement-invariant norms in Sobolev imbedding inequalities 18 pages, pdf file 226 kB
Published in Studia Math 206, 2 (2011), 97-119.
... and therefore removed from the preprint server. Mail to the author(s) for reprints.

MATH-KMA-2008/271

 Petr Holicky: Borel bimeasurable mappings of complete metric spaces, their decompositions and fibres 15 pages, pdf file 183 kB
Published in Topology and its Applications 156 (2008), pp. 217-226.
... and therefore removed from the preprint server. Mail to the author(s) for reprints.

MATH-KMA-2008/272

 Lubos Pick: Optimality of function spaces in Sobolev embeddings 23 pages, pdf file 290 kB
Published in Sobolev Spaces in Mathematics I. Sobolev Type Inequalities. International Mathematical Series, Vol 8, Springer, Tamara Rozhkovskaya Publisher, Vladimir Maz´ya (Ed.), xxix + 378 pages, ISBN 978-0-387-85647-6, 2009, 249-280.
... and therefore removed from the preprint server. Mail to the author(s) for reprints.

MATH-KMA-2008/273

 Jiri Spurny: Borel sets and functions in topological spaces 18 pages, pdf file 229 kB
Published in Acta Mathematica Hungarica 129(1-2) (2010), 47-69.
... and therefore removed from the preprint server. Mail to the author(s) for reprints.

MATH-KMA-2008/274

 Miroslav Kacena, Jiri Spurny: Affine Baire functions on Choquet simplices 9 pages, pdf file 164 kB
Published in Cent. Eur. J. Math. 9(1) (2011), 127-138.
... and therefore removed from the preprint server. Mail to the author(s) for reprints.

MATH-KMA-2008/275

 Jiri Jelinek, Dalibor Prazak: On the sign of Colombeau functions and applications to conservation laws 20 pages, pdf file 244 kB
Published in Comment. Math. Univ. Carolinae 50 (2009), no. 2, 221-243.
... and therefore removed from the preprint server. Mail to the author(s) for reprints.

MATH-KMA-2008/276

 Warren B. Moors, Jiri Spurny: On the topology of pointwise convergence on the boundaries of $L_1$-preduals 9 pages, pdf file 189 kB
Published in Proceedings of the American Mathematical Society 137(4) (2009), 1421-1429.
... and therefore removed from the preprint server. Mail to the author(s) for reprints.

MATH-KMA-2008/277

 Hugo Beirao da Veiga, Petr Kaplicky, Michael Ruzicka: Boundary regularity of shear thickening flows 31 pages, pdf file 340 kB
Published in J. Math. Fluid Mech. 13 (2011), no. 3, 387-404.
... and therefore removed from the preprint server. Mail to the author(s) for reprints.

MATH-KMA-2008/278

 Petr Hajek, Gilles Lancien, Antonin Prochazka: Weak$^*$ dentability index of spaces $C([0,\\alpha])$ 7 pages, pdf file 192 kB
Published in Journal of Mathematical Analysis and Applications 353 (2009), 239-243.
... and therefore removed from the preprint server. Mail to the author(s) for reprints.

MATH-KMA-2008/279

 Robert Deville, Antonin Prochazka: A parametric variational principle and residuality 21 pages, pdf file 209 kB
Published in J. Funct. Anal. 256 (2009), no. 11, 3568–3587.
... and therefore removed from the preprint server. Mail to the author(s) for reprints.

MATH-KMA-2008/280

 Michal Kraus: A note on the uniform approximation of continuous affine functions 5 pages, pdf file 152 kB
Published in Expo. Math. 27 (2009) 73–78.
... and therefore removed from the preprint server. Mail to the author(s) for reprints.

MATH-KMA-2008/281

 Tomas Barta: Smooth solutions of Volterra equations via semigroups 12 pages, pdf file 201 kB
Published in Bull. Austral. Math. Soc. 78, 2008, 249--260.
... and therefore removed from the preprint server. Mail to the author(s) for reprints.

MATH-KMA-2008/282

 Tomas Barta: Delayed quasilinear evolution equations with $BV$-coefficients 13 pages, pdf file 233 kB
Published in Z. Anal. Anwend. 29 (2010), no. 2, 149–162.
... and therefore removed from the preprint server. Mail to the author(s) for reprints.

MATH-KMA-2008/283

 Libor Vesely, Ludek Zajicek: On extensions of d.c. functions and convex functions 16 pages, pdf file 277 kB
Published in J. Convex Anal. 17 (2010), no. 2, 427–440.
... and therefore removed from the preprint server. Mail to the author(s) for reprints.

MATH-KMA-2008/284

 Ondrej Kalenda, Wieslaw Kubis: The structure of Valdivia compact lines 18 pages, pdf file 210 kB
Published in Topol. Appl. 157 (2010), no. 7, 1142-1151.
... and therefore removed from the preprint server. Mail to the author(s) for reprints.

MATH-KMA-2008/285

 Petr Holicky: Borel classes of uniformizations of sets with large sections 12 pages, pdf file 171 kB
Published in Fundamenta Math. 207 (2010), 145--160.
... and therefore removed from the preprint server. Mail to the author(s) for reprints.

MATH-KMA-2008/286

 Salvatore Leonardi, Jana Stara: Regularity results for the gradient of solutions of linear elliptic systems with $VMO$-coefficients and $L^{1,\\lambda}$ data 52 pages, pdf file 320 kB
Published in Forum Math. 22 (2010), no. 5, 913–940.
... and therefore removed from the preprint server. Mail to the author(s) for reprints.

MATH-KMA-2008/287

 Andrea Cianchi, Lubos Pick: Optimal Gaussian Sobolev embeddings 38 pages, pdf file 359 kB
Published in J. Funct. Anal. 256, 11 (2009), 3588-3642.
... and therefore removed from the preprint server. Mail to the author(s) for reprints.

MATH-KMA-2008/288

 Andrea Cianchi, Lubos Pick: An optimal endpoint trace embedding 9 pages, pdf file 145 kB
Published in Ann. Inst. Fourier (Grenoble) 60, 3 (2010), 939-951.
... and therefore removed from the preprint server. Mail to the author(s) for reprints.

MATH-KMA-2008/289

 Robert Cerny, Stanislav Hencl, Jan Kolar: Integral functionals that are continuous with respect to the weak topology on $W^{1,p}_{0}(\\Omega)$ 19 pages, pdf file 290 kB
Published in Nonlinear Analysis 71 (2009) no.7-8, 2753-2763.
... and therefore removed from the preprint server. Mail to the author(s) for reprints.

MATH-KMA-2008/290

 Jaroslav Lukes, Lubos Pick, Dusan Pokorny: On geometric properties of the spaces $L^{p(x)}$ 12 pages, pdf file 168 kB
Published in Rev. Mat. Complutense 24, 1 (2011), 115-130.
... and therefore removed from the preprint server. Mail to the author(s) for reprints.

MATH-KMA-2008/291

 Miroslav Husek, Antonio Pulgarin: Lattice-ordered groups of real continuous functions 9 pages, pdf file 184 kB
Submitted to Topology and its Applications


text:
Browse Questions

# An abnormal increase in the cell number due to the infection is called :

$\begin {array} {1 1} (1)\;Hyperplasia & \quad (2)\;Hypertrophy \\ (3)\;Hypoplasia & \quad (4)\;Necrosis \end {array}$


text:
X

DAYS

:

HOUR

:

MINS

:

SEC

Copied to Clipboard
Basic Accuracy: 34.39% Submissions: 100k+ Points: 1

Create a link list of size N according to the given input literals. Each integer input is accompanied by an indicator which can either be 0 or 1. If it is 0, insert the integer in the beginning of the link list. If it is 1, insert the integer at the end of the link list.
Hint: When inserting at the end, make sure that you handle NULL explicitly.

Example 1:

Input:
Output: 5 2 9 5 6
Explanation:
Length of Link List = N = 5
9 0 indicated that 9 should be
inserted in the beginning. Modified
5 1 indicated that 5 should be
inserted in the end. Modified Link
List = 9,5.
6 1 indicated that 6 should be
inserted in the end. Modified Link
List = 9,5,6.
2 0 indicated that 2 should be
inserted in the beginning. Modified
5 0 indicated that 5 should be
inserted in the beginning. Modified
Final linked list = 5, 2, 9, 5, 6.

Example 2:

Input:
Output: 5 6 9

You only need to complete the functions insertAtBeginning() and
insertAtEnd() that takes the head of link list and integer value of the data to be inserted as inputs and returns the head of the modified link list.

Expected Time Complexity: O(1) for insertAtBeginning() and O(N) for insertAtEnd().
Expected Auxiliary Space: O(1) for both.

Constraints:
1 <= N <= 104

We are replacing the old Disqus forum with the new Discussions section given below.


text:
# Statistical decision theory: a decision-theoretic approach to the estimation of an unknown...

Statistical decision theory: a decision-theoretic approach to the estimation of an unknown parameter θ introduces the loss function L(θ, a) which, loosely speaking, gives the cost of deciding that the parameter has the value a, when it is in fact equal to θ. The estimate a can be chosen to minimize the posterior expected loss,

This optimal choice of a is called a Bayes estimate for the loss function L. Show the following:

(a) If L(θ, a)=(θ−a)2 (squared error loss), then the posterior mean, E(θ|y), if it exists, is the unique Bayes estimate of θ.

(b) If L(θ, a)=|θ−a|, then any posterior median of θ is a Bayes estimate of θ.

(c) If k0 and k1 are nonnegative numbers, not both zero, and

then any k0/(k0+k1) quantile of the posterior distribution p(θ|y) is a Bayes estimate of θ.

## Plagiarism Checker

Submit your documents and get free Plagiarism report

Free Plagiarism Checker


text:
# Header for page

Jump to: navigation, search

Hi Patricia, There appears to be a typo in the header and URL for this page ('CCost'), but I don't know how to fix something like that.

04:11, 23 November 2007


text:
Simulating a bivariate Ito process

I would like to simulate a bivariate process where the two components, say $$X_1(t)$$ and $$X_2(t),$$ which are related by the following stochastic differential equations:

dX_1(t) = -X_2(t)dt + \sigma_1dW^{(1)}(t)
and
dX_2(t) = X_1(t)dt + \sigma_2dW^{(2)}(t).

I would also like to allow the two BMs $$W^{(1)}$$ and $$W^{(2)}$$ that are correlated.

What would be the proper way to do this by defining a process using ItoProcess first and then simulating it via RandomFunction? If the coefficients were just a function of $$t$$ and not of $$X_i(t,$$ then I am able to make it work, but everytime I try to enter the process as described in the two SDEs above, I get some error message to the tone that "process" does not exist.

Any help much appreciated. I tried to make sense of what Mathematica has for explanation in the online help, but it does not seem to solve my issues.

Thank you.

Maurice

• Maybe a starting point here. Jul 8 '20 at 20:15
• I was already aware of that thread. It works fine, but as long as my drifts and diffusions are not functions of the processes involved themselves. I do believe that what I did is a modification of that, but alas, cannot get it to work in my setting. Jul 9 '20 at 1:04

One could define a process:

proc[x10_, x20_, \[Sigma]1_, \[Sigma]2_, \[Rho]_] :=
ItoProcess[{
\[DifferentialD]x1[t] == -x2[t]\[DifferentialD]t + \[Sigma]1 \[DifferentialD]Wa[t],
\[DifferentialD]x2[t] == x1[t]  \[DifferentialD]t + \[Sigma]2 (\[Rho] \[DifferentialD]Wa[t] + Sqrt[1 - \[Rho]^2] \[DifferentialD]Wb[t])},
{x1[t], x2[t]}, {{x1, x2}, {x10, x20}}, {t, 0},
{Wa \[Distributed] WienerProcess[], Wb \[Distributed] WienerProcess[]}]

and then use it:

Mean[proc[x10, x20, \[Sigma]1, \[Sigma]2, \[Rho]][t]]
(* {x10 Cos[t] - x20 Sin[t], x20 Cos[t] + x10 Sin[t]} *)

This matches the analytical result:

$$x_1(t)=-\imath\ (y_1(t)-y_2(t))$$ $$x_2(t)=y_1(t)+y_2(t)$$ $$y_1(t)=e^{-\imath\ t}\left[ y_1(0)+\frac{1}{2}\int_0^{t}\ e^{\imath\ \tau}\ \left(\imath\ \sigma_1 dW_a\ +\ \sigma_2 dW_b \right)\right]$$ $$y_2(t)=e^{\imath\ t}\left[ y_2(0)+\frac{1}{2}\int_0^{t}\ e^{-\imath\ \tau}\ \left(-\imath\ \sigma_1 dW_a\ +\ \sigma_2 dW_b \right)\right]$$

Other properties (covariance, ...) could be checked along the same lines.

• That is excellent. Thank you. Jul 9 '20 at 15:42


text:
# Polar to Rectangular Coordinates

Problem: Transform the following equation from polar to rectangular coordinates. \begin{eqnarray*} \rho &=& \frac{2}{1 - \cos \theta} \\ \end{eqnarray*}

Let's check with $\theta=60^\circ$ so that $\rho=4$. Then: $x=2$, $y=2\sqrt3$, $y^2=12$. But $4(x+2)=16$ and $4x+4=12$. So you are right and the book is wrong.
• Perhaps even easier, check at $\theta = \frac\pi2$ ($90$ degrees). Then $\cos\theta = 0$, $x=0$, and $\rho = 2$, hence $y = 2$ and $y^2 = 4$. The book says $y^2$ would be $8$ when $x = 0$. – David K Sep 5 '15 at 22:46


text:
Fundamental Limits of Invisible Flow Fingerprinting

Network flow fingerprinting can be used to de-anonymize communications on anonymity systems such as Tor by linking the ingress and egress segments of anonymized connections. Assume Alice and Bob have access to the input and the output links of an anonymous network, respectively, and they wish to collaboratively reveal the connections between the input and the output links without being detected by Willie who protects the network. Alice generates a codebook of fingerprints, where each fingerprint corresponds to a unique sequence of inter-packet delays and shares it only with Bob. For each input flow, she selects a fingerprint from the codebook and embeds it in the flow, i.e., changes the packet timings of the flow to follow the packet timings suggested by the fingerprint, and Bob extracts the fingerprints from the output flows. We model the network as parallel M/M/1 queues where each queue is shared by a flow from Alice to Bob and other flows independent of the flow from Alice to Bob. The timings of the flows are governed by independent Poisson point processes. Assuming all input flows have equal rates and that Bob observes only flows with fingerprints, we first present two scenarios: 1) Alice fingerprints all the flows; 2) Alice fingerprints a subset of the flows, unknown to Willie. Then, we extend the construction and analysis to the case where flow rates are arbitrary as well as the case where not all the flows that Bob observes have a fingerprint. For each scenario, we derive the number of flows that Alice can fingerprint and Bob can trace by fingerprinting.

There are no comments yet.

Authors

• 6 publications
• 9 publications
• 59 publications
• 24 publications
• Towards Provably Invisible Network Flow Fingerprints

Network traffic analysis reveals important information even when message...
11/28/2017 ∙ by Ramin Soltani, et al. ∙ 0

• Data Flow Dissemination in a Network

We consider the following network model motivated, in particular, by blo...
10/18/2021 ∙ by Aditya Gopalan, et al. ∙ 0

• Non-clairvoyant Scheduling of Coflows

The coflow scheduling problem is considered: given an input/output switc...
04/13/2020 ∙ by Akhil Bhimaraju, et al. ∙ 0

• Fingerprint based bio-starter and bio-access

In the paper will be presented a safety and security system based on fin...
08/21/2003 ∙ by G. Iovane, et al. ∙ 0

• DeepCorr: Strong Flow Correlation Attacks on Tor Using Deep Learning

Flow correlation is the core technique used in a multitude of deanonymiz...
08/22/2018 ∙ by Milad Nasr, et al. ∙ 0

• A Theory of Traffic Regulators for Deterministic Networks with Application to Interleaved Regulators

We define the minimal interleaved regulator, which generalizes the Urgen...
01/25/2018 ∙ by Jean-Yves Le Boudec, et al. ∙ 0

• Evaluation of Elephant-based Algorithms for Flow Table Reduction under Realistic Traffic Distributions

The majority of Internet traffic is caused by a relatively small number ...
05/01/2020 ∙ by Piotr Jurkiewicz, et al. ∙ 0

This week in AI

Get the week's most popular data science and artificial intelligence research sent straight to your inbox every Saturday.

I Introduction

Given the presence of communication systems in daily life and their rapid growth, e.g., cellular networks, internet of things, etc., security and privacy has emerged as a vital area of research and development [2, 3, 4, 5, 6, 7, 8, 9]. For every communication system, security involves not only allowing authorized users to communicate a message in a way that the message content is protected from unauthorized users, but also preventing access by malicious users. Hence, breaking the anonymity of users in an anonymous network such as Tor, Bitblinder, and Darknet plays a major role in preventing malicious use of technology.

Even if the messages are encrypted, traffic analysis can be used to infer sensitive information from the packet characteristics such as timing patterns, sizes, and packet rates. For instance, packet timings can reveal information about passwords sent over SSH channels [10]. Also, traffic analysis can discover stepping stone attacks where malicious users employ compromised computers to relay their traffic [11, 12]. Furthermore, it can be used to find correlations between input and output links of a network to reveal connections between the links [13].

Unlike passive traffic analysis which involves only recording traffic characteristics, such as packet timings, active traffic analysis involves both recording and modifying traffic characteristics to embed information in them. For instance, in flow watermarking [14, 15, 16], watermarks are embedded into flows by changing their packet timings according to a unique secret pattern. Therefore, each flow contains one bit of information indicating whether it contains the watermark. However, in flow fingerprinting, the embedded patters are used to communicate information such as the identity of the party that performed fingerprinting [17], the location of the flow in the network where it was fingerprinted [1], and the time when the fingerprint was embedded. Thus necessarily this will convey more than one bit of information.

Active traffic analysis has emerged as a vibrant area of research recently. In [18], the authors propose detecting stepping stones using flow watermarking. Peng et al. [19] show that this method is detectable and propose attacks on it. Wang et al. [20] show that the anonymity of VoIP calls made over an anonymity network can be broken using watermarking methods. Kiyavash et al. [21] propose a multi-flow attack on interval-based watermarking methods, which delay packets of specific intervals based on the value of the watermarks. Houmansadr et al. propose RAINBOW watermarking [14] and SWIRL [15] which is a scalable traffic analysis method resilient against aggregated-flows attacks. They also study the capacity of flow watermarking [22] and propose a flow fingerprinting scheme allowing fingerprinting of millions of flows by perturbing the packet timings of relatively short lengths of flows [23]. Rezaei et al. [24] introduce an active fingerprinting method called TagIt that works by slightly delaying packets into secret time intervals.

We consider the following problem: in a time interval of length , can Alice and Bob perform fingerprinting to link input and output flows of the network without being detected by Willie, and if yes, how can they do so and what is the maximum number of flows that they can link reliably? For the case where packet timings of each flow is an independent instantiation of a Poisson process, we present the construction and analysis, and calculate the asymptotic expression for as a function of . We first assume flow packet rates are equal and that Bob observes only flows with fingerprints and consider two main scenarios: 1) Alice fingerprints all flows she observes; 2) Alice fingerprints a subset of the flows, and the subset is unknown to Willie. Then, we present the extensions to arbitrary flow rates as well as the case where Bob observes a set of flows in which not all flows are fingerprinted.

The remainder of the paper is organized as follows. We present the system model, definitions, and invisibility and reliability metrics employed in this paper in Section II. Then, in Sections III and IV, we present constructions and analyses for the two main fingerprinting scenarios. In Section V, we present the extensions of the main scenarios to arbitrary flow rates, and in Section VI, we present the extensions of the main scenarios to the case where Bob observes flows with and without fingerprints. Section VII discusses the results, and Section VIII discusses future work. We conclude in Section IX.

Ii System Model, Definitions, and Metrics

Ii-a System Model

We consider a set of flows between pairs of input and output links. We assume the links are known but not the pairings. Also present are two parties Alice and Bob whose goal is to identify some or all of the pairings by fingerprinting, without a third party, Willie, detecting this identification. Moreover, Alice and Bob wish to do so within the time interval . Alice, Bob, and Willie know that all packet timings are governed by Poisson processes and they the rate of each flow that they observe.

Alice has access to a subset of the input links where each link conveys a packet flow . She is allowed to buffer packets and release them from her buffer but no other operations (e.g., inserting packets, changing packet ordering). Willie is located between Alice and the network, and he watchfully observes all of the input links accessed by Alice () to detect whether or not Alice is fingerprinting flows (see Fig. 1). Willie is able to verify the sources and the order of the packets. Therefore, if Alice inserts a packet of her own or re-orders the packets on any of the links to transmit information to Bob, Willie will detect her immediately. Bob observes a subset of the output links where each link conveys a packet flow . He is only allowed to observe the time of the arrival of each of the packets in each flow. Bob and Willie cannot manipulate the flows (e.g., change packet timings, remove packets, insert packets, change packet ordering).

Prior to fingerprinting, Alice generates a codebook of fingerprints and shares it with Bob. The codebook is secret, and thus Willie does not have access to it. On the other side of the network, Bob uses the codebook to extract the fingerprints and identify the flows.

Each fingerprint (codeword) of the codebook corresponds to a sequence of inter-packet delays, which plays the role of a unique flow identifier. Alice embeds a unique fingerprint in each flow, i.e., she buffers packets of each flow and releases them according to timings associated with a fingerprint. We denote by the set of flows with fingerprints. In general, not every fingerprinted flow is observed by Bob. However, since our goal is to calculate the maximum number of flows that can be traced by Alice and Bob, we assume Bob observes all fingerprinted flows, i.e., .

As Willie is only able to read the channel, he cannot change packet timings; however, packet timings change after they pass through the network. Nevertheless, we present a construction where Bob can successfully identify the flows.

We model the network as parallel First In First Out (FIFO) queues with exponential service times ( queues). We consider two settings for the network:

1. Setting 1: each queue is shared by the flow Alice and Bob are monitoring, which we refer to it as “main flow”, and other flows independent of the main flow, which we refer to them as “interfering flows”. (see Fig. 0(a)).

2. Setting 2: each queue conveys just the flow Alice and Bob are monitoring (see Fig. 0(b)).

Denote by the queue, and by , , and the service rate, the input rate, and the sum of the rates of the interfering flows at , respectively. We term the effective service rate [25] of and we assume Alice knows the effective service time of all queues . The queues are stable, i.e., .

First, we consider Setting 1 (shown in Fig. 0(a)). Assuming the flow rates of the flows observed by Alice and Bob are the same () and that Bob observes only the set of fingerprinted flows (), we present two scenarios:

• Scenario 1 (analyzed in Section III): Alice fingerprints all flows to which she has access ().

• Scenario 2 (analyzed in Section IV): Alice fingerprints a subset of the flows to which she has access ().

Then, considering the same setting for the network (Setting 1 shown in Fig. 0(a)), we present Scenarios 3 and 4 which are extensions of Scenarios 1 and 2, respectively, to the case that flow rates are arbitrary. Scenarios 3 and 4 are analyzed in Sections V-A and V-B, respectively. Next, we consider Setting 2 (shown in Fig. 0(b)) and present Scenarios 5 and 6, which are extensions of Scenarios 1 and 2, respectively, to the case that Bob observes fingerprinted flows as well as other flows that are not fingerprinted (). If Bob observes a flow that is not fingerprinted, the flow can be either coming from Alice () or other inputs of the network (). Scenarios 5 and 6 are analyzed in Sections VI-A and VI-B, respectively. We show that in each scenario Alice can fingerprint the flows invisible to Willie but distinguishable by Bob. In addition, we determine the number of flows that Alice and Bob can invisibly and reliably trace by fingerprinting.

Next, we present definitions and describe invisibility and reliability metrics.

Ii-B Definitions

Willie uses hypothesis testing to detect whether Alice is fingerprinting:

• : Alice is not fingerprinting.

• : Alice is fingerprinting.

Denote by

the probability of rejecting

when it is true (type I error or false alarm), and by

the probability of rejecting

when it is true (type II error or missed detection). To give more power to Willie, we assume he knows the probability that Alice is fingerprinting,

.

Similar to the definition of covertness [26, 27, 28, 29, 30], we define invisibility[1]:

Definition 1.

(Invisibility) Alice’s fingerprinting is invisible (covert) if and only if she can lower bound Willie’s probability of error, , by for any , as . We term the invisibility parameter.

Definition 2.

(Reliability) Alice’s fingerprinting is reliable if and only if for any and any flow, the probability of the failure event satisfies as . We term the reliability parameter. For a flow with a fingerprint the failure event occurs when one of the following events occurs:

• Alice cannot successfully fingerprint the flow since she does not have a packet available to release when she needs one. We denote by the probability of this event.

• Bob cannot extract the fingerprint successfully. We denote by the probability of this event.

For a flow without a fingerprint, the failure event occurs when Bob detects a fingerprint. We denote by the probability of this event.

Definition 3.

(Lambert-W function) The Lambert-W function is the inverse function of .

We present results under the assumption that . We show in Appendix IX that this results in invisibility for the general case where . In this paper, we use standard Big-O, Little-o, Big-Omega, little-omega, and Big-Theta notations [31, Ch. 3].

Iii Scenario 1: All flows are fingerprinted, Setting 1

Consider Scenario 1: Alice fingerprints all flows she observes (), and Bob observes only the fingerprinted flows (). All of flow rates are equal (). We consider Setting 1 (see Fig. 0(a)), i.e., parallel queues where each queue is shared by a fingerprinted flow and other interfering flows independent of the fingerprinted flow. Alice fingerprints the input flows during time interval , and Bob extracts the fingerprints from the flows on the output links of the network to infer the connections between input and output flows.

Alice buffers packets and releases them according to a fingerprint. She uses a secret codebook where each codeword (fingerprint) is a unique flow identifier consisting of a sequence of inter-packet delays. Because the timings of packets that Alice receives as well as the codewords are random, Alice will face a causality problem: the need to send a packet before she receives it. We give an example of when Alice cannot successfully fingerprint a flow in Fig. 2.

Consider a flow and assume the inter-arrival times of this flow before Alice makes any changes are . Also assume Alice selects a fingerprint from her codebook. Note that the inter-arrival time between the first and second packets of the flow is but Alice has to alter the packet timings of the flow to achieve an inter-arrival of between the first and the second packets. In other words, she has to send the second packet before she receives it.

To account for this, prior to fingerprinting, Alice invisibly slows down the flow in order to buffer packets [28, Section IV]. This ensures she will have a packet in her buffer to transmit at the appropriate times and can fingerprint the flow successfully.

We calculate the number of flows that Alice and Bob can trace by fingerprinting using this scheme, asymptotically as a function of .

Theorem 1.

Consider Setting 1 (see Fig. 0(a)). If Alice fingerprints all input flows () whose rates are equal () and Bob only observes fingerprinted flows (), then Alice and Bob can invisibly and reliably trace flows in a time interval of length .

Construction: Per above, Alice uses a scheme consisting of two phases of lengths and , and employs a codebook of fingerprints to embed in the flows. The codebook construction is similar to the one adopted in [1, 28, 29]. In particular, Alice generates independent instantiations of a Poisson process with parameter , where is the length of the second phase, as follows. To generate the codeword (), first a number

is generated according to a Poisson distribution with mean

, and then points are distributed randomly and uniformly in a time interval of length  [32] (see Fig. 4). Therefore, the codebook contains fingerprints (codewords) . Alice selects a fingerprint for each flow and applies the inter-packet delays of the chosen fingerprint to the packets of the flow. The codebook is shared with Bob, not know to Willie.

Alice divides the time interval of length into two phases (see Fig. 3):

• Phase 1 (buffering phase) of length : Alice slows each flow from rate to rate to buffer packets, i.e., if she receives a packet at time , she transmits it at time . This allows her to build up a backlog of packets in her buffer which ensures that she will be able to fingerprint each flow during the next phase successfully.

• Phase 2 (fingerprinting phase) of length : for each flow, she selects a fingerprint from her codebook and then alters the packet timings of the flow according to the selected fingerprint.

The lengths of the two phases are,

 T1 =Tmα1+mα, (1) T2 =T−T1=T1+mα, (2)

where is a constant defined later, and is the number of flows to be fingerprinted.

Analysis: (Invisibility) Similar to the analysis of covertness in [28, Theorem 2], we can show that Alice’s fingerprinting is invisible. Consider the first phase. We can show that for all , Alice can slow down the flows from rate to rate , and achieve (see the proof in Appendix IX)

 P(w)e>12−ϵ, (3)

where is Willie’s error probability. Thus, her buffering is invisible. In the second phase, the packet timings for each flow is an instantiation of a Poisson process with rate and hence the traffic pattern is indistinguishable from the pattern that Willie expects to observe. Hence, the scheme is invisible.

(Reliability) Now, we show that Alice’s fingerprinting satisfies all of the conditions in Definition 2, and thus is reliable. Note that all flows have fingerprints. By the union bound:

 Pf≤Pf1+Pf2. (4)

Thus, to show the fingerprinting is reliable, it suffices to show that for all .

First, we show that as for each flow, i.e., Bob can successfully extract a fingerprint from each flow. Recall that Alice fingerprints all flows that she observes and Bob observes only the flows fingerprinted by Alice (). Therefore, , where denotes the cardinality of a set.

Without loss of generality, we assume that flow passes through the queue (). Denote by the capacity of for the transmission of information via packet timings. Recall that is an queue with multiple inputs and outputs. Then [25, Proposition 1]:

 Ci≥λlog((μi−λ′i)/λ), (5)

where is the sum of rates of the interfering flows passing through , and is the service rate of . From [32, Definition 1], the rate of the codebook is , and  [32, Definition 2], (5) implies that all transmission rates smaller than result in a decoding error probability that tends to zero as . Therefore, we require

 logmT2<λlog((μi−λ′i)/λ) (6)

for Bob to successfully extract the fingerprint from . Note that (6) holds for all . Hence, as long as

 logmT2

where

 C=λlog(mini{μi−λ′i}/λ), (8)

for each flow . Note that (2) implies that as . Therefore,

 Pf2→0 as T→∞. (9)

Next, we show that , i.e., Alice can successfully fingerprint the flows. Recall that Alice accounts for the causality problem by buffering packets before she starts fingerprinting. Since in the first phase Alice slows down the packet rate from rate to rate , on average she can buffer

packets. Consequently, we can apply the weak law of large numbers (WLLN) to show that the probability that Alice buffers more than

packets tends to one, as tends to infinity. Now, we have to answer this question: noting that Alice has packets in her buffer, what is the probability that Alice cannot successfully fingerprint ?

Because Alice receives and transmits packets on each flow according to two independent Poisson processes of rate , and the Poisson process is memoryless, we model the process as a symmetric random walk on a 1-D grid to answer this question [28]. The location of the walker corresponds to the number of packets in Alice’s buffer. The walker goes from location to when Alice receives a packet, and goes from location to when Alice transmits a packet. Denote by the probability of the event that the walker starting from the location reaches the point , at least once, during the time . Then [28, Eq. (27)]:

 limt→∞Pk,t≤1−limt→∞erf(k√8λt). (10)

Since Alice fingerprints the flows in the second phase, . Recall that the probability that Alice buffers more than packets tends to one, as . Therefore, we let . By (10), the probability that Alice runs out of packets for flow satisfies:

 limT→∞Pf1≤1−limT→∞erf(ϵ2√T12mT2)=1−erf(ϵ√α8). (11)

where the equality holds since following from (1) and (2). Note that (11) is independent of (index of the flow), and holds for all flows , . Let

 α =(8/ϵ2)(erf−1(1−ζ))2. (12)

By (12), (11) yields

 Pf1≤ζ as T→∞. (13)

Consequently, by (4), (9), (13), for all , when and thus Alice and Bob’s fingerprinting is reliable.

(Number of flows) By (7) and (2), we require

 logmT2=(1+mα)logmT

as (). We show that we can achieve (14) as long as

 m=12min{α−1(TCW(TC)−1),TCW(TC)}. (15)

Consider the following fact:

Fact 1.

For , if , where is the Lambert-W function, then .

Proof. Assume . First, we show that . From the definition of the Lambert-W function, . Therefore, . Consequently,

 x′logx′=yW(y)logyW(y)=yW(y)W(y)=y. (16)

Since , implies that . Because is an increasing function of , , and the proof is complete.

Next, for both cases and we show that , which implies (14). Consider . Note that (15) implies . Therefore, Fact 1 yields:

 TC>mlogm.

Since ,

 TC>mlogm>(1+mα)logm.

Now, consider . Note that (15) implies that , which implies:

 1+mα

By (17) and Fact 1,

 TC >(1+mα)log(1+mα)≥(1+mα)logm,

where the last inequality follows from . Consequently, (15) satisfies (14). Since for , , Alice and Bob can invisibly and reliably pair the end points of every flow, and thus break the anonymity of a network (Setting 1 shown in Fig. 0(a)) with flows.

Iv Scenario 2: Alice fingerprint a subset of the flows, Setting 1

In Scenario 1, Willie is certain that if is true, i.e., Alice fingerprints, then all flows are slowed down in the first phase. In Scenario 2, we add uncertainty to Willie’s knowledge under : Alice fingerprints a subset of the flows, and is unknown to Willie. Therefore, Willie has to investigate a large set of flows to detect if some are slowed down in the first phase as required for fingerprinting. We show that Willie’s uncertainty allows Alice to fingerprint more flows without being visible.

Alice fingerprints a subset of the flows she observes (). For each flow, she selects a unique fingerprint from her codebook and alters the timings of that flow according it. Similar to Scenario 1, Alice has units of time which she divides into two phases: a buffering phase of length , which ensures Alice can successfully fingerprint, and a fingerprinting phase of length . Bob, who has access to the fingerprint codebook and observes the set of fingerprinted flows (), extracts the fingerprints from the flows. The fingerprint codebook is secret and Willie does not have access to it. The network is modeled by parallel queues with each queue shared by a flow from Alice to Bob (main flow) as well as other interfering flows independent of the main flow (Setting 1 shown in Fig. 0(a)). We calculate the number of flows () that Alice can fingerprint using this scheme, asymptotically as a function of .

Theorem 2.

Consider Setting 1 (see Fig. 0(a)). In a set containing flows with equal rates (), if Bob observes only the fingerprinted flows (), Alice and Bob can invisibly and reliably trace flows in a time interval of length , where

 m=⎧⎪⎨⎪⎩M,M=O(1)o(min{√M,eTC1}),M=ω(1) \& M=O(e2TC)Θ(eTC2),M=ω(e2TC) (18)

is given in (8), and arbitrary constants .

A more accurate characterization of with respect to is presented in (32) in the proof below.

Construction: The construction is similar to that of Scenario 1 except that Alice fingerprints a subset of the flows that she observes. Recall that all of flows observed by Bob are also observed by Alice (). Alice knows which set of her flows will be observed by Bob, and chooses them for fingerprinting (). Note that Willie does not know which subset of is . Alice generates a codebook of fingerprints (similar to Scenario 1) and shares it with Bob prior to fingerprinting, where is given in (18). Recall that we calculate the maximum number of flows that Alice and Bob can trace; therefore, we only consider the case which can be extended to trivially.

Alice’s scheme consists of two phases, a buffering phase of length , and a fingerprinting phase of length , where

 T1 =Tα′ln(1+ϵ2M2m2)+α′, (19) T2 =T−T1=T1+α′/ln(1+ϵ2M2m2), (20) α′ =αϵ2. (21)

Recall that and are given in (12) and (8), respectively, and is the invisibility parameter. Alice generates fingerprints for her codebook analogous to Scenario 1. The number of fingerprints in her codebook is .

Analysis: (Invisibility) For each phase, we show that all operations Alice performs on the flows are invisible. Consider the first phase where Alice slows down each flow from rate to rate with

 Δ=√λT1ln(1+ϵ2M2m2). (22)

From Willie’s perspective, the number packets in time is a sufficient statistic to detect Alice [28]. If Alice does not fingerprint (

), then the joint probability density function (pdf) of Willie’s observations is

 P0 =M∏i=1Pλ(ni),

where is the pdf of a Poisson random variable with mean . Note that Willie knows that out of flows observed by Alice is selected to be fingerprinted, but he does not know which set is selected. Therefore, from Willie’s point of view, if Alice chooses to fingerprint flows (), then each flow will contain a fingerprint with probability

 p=mM. (23)

Thus, the joint pdfs of Willie’s observations when Alice fingerprints () is

 P1 =M∏i=1(pPλ−Δ(ni)+(1−p)Pλ(ni)),

where is the change in flow rate. Note that the change of rate differs from the one in Scenario 1. Suppose that Willie applies an optimal hypothesis test to minimize his probability of error . Then, we can obtain a lower bound on his probability of error[soltani2017covert, Eq.1]:

 P(w)e≥12−√18D(P1||P0), (24)

where

is the Kullback–Leibler divergence (relative entropy) between

and .

Alice’s scheme is invisible as long as she can make Willie’s detector operate as close as desired to the detector that disregards Willie’s observations and results in (see Definition 1). Next, we show that for arbitrary , , and then we apply (24) to prove Alice’s buffering is invisible. Observe:

 D(P1||P0) (a)=MD(pPλ−Δ(n)+(1−p)Pλ(n)||Pλ(n)), (b)=ME1[ln(pPλ−Δ(n)+(1−p)Pλ(n)Pλ(n))], =ME1[ln(peΔT1(λ−Δλ)n+(1−p))], (25) (c)≤MpE1[eΔT1(λ−Δλ)n]−Mp(d)=Mp2(eΔ2T1/λ−1)(e)=ϵ2/2. (26)

where

follows from the chain rule for relative entropy

[33, Eq. (2.67)], denotes expected value with respect to the pdf , follows from the definition of the Kullback–Leibler divergence, is true since , is true since

 E1[(λ−Δλ)n]=e−ΔT1(peΔ2T1/λ+(1−p)),

and follows from substituting the values of , , and given in (22), (23), and (19) respectively. By (24) and (25),

 P(w)e≥12−ϵ, (27)

as , and thus Alice’s buffering is invisible.

The second phase is invisible because the fingerprints are samples of Poisson processes with rate . Combined with the invisibility of the first phase, Alice and Bob’s scheme is invisible.

(Reliability) The analysis is similar to that of Scenario 1. Since all flows observed by Bob are fingerprinted (), to show Alice and Bob’s scheme is reliable, it suffices to show that for each flow for all .

Upper bounding is similar to that of Scenario 1. The first difference is in the number of packets that Alice can buffer from each flow in the first phase. Here, since Alice slows down each flow from rate to , where is given in (22), the probability that Alice can buffer more than packets in the second phase tends to one as . Therefore, letting and in (10) yields:

 limT→∞Pf1≤1−limT→∞erf⎛⎜ ⎜⎝ ⎷T1ln(1+ϵ2M2m2)8T2⎞⎟ ⎟⎠. (28)

The second difference in the analysis of is due to differences in the expressions for and . By (19) and (20), . Therefore, (28) yields:

 limT→∞Pf1≤1−erf(√α′8)=1−erf(ϵ√α8), (29)

where the last step is true since . By (12),

 Pf1≤ζ as T→∞. (30)

Now, consider Bob’s decoding error for each flow, . By (19) and (20), as . In order for Bob to be able to successfully extract the fingerprint from each flow, we require

 logmT2

as (). Substituting from (20) and re-arranging yields:

 m≤exp⎛⎜⎝TC1+α′/ln(1+ϵ2M2m2)⎞⎟⎠ (32)

We show in Appendix IX that (32) holds asymptotically as , given the value of provided in (18).

Consequently,

 Pf2→0 as T→∞. (33)

By (4), (30), and (33), as . Thus, if , Alice can invisibly and reliably fingerprint flows in a time interval of length , and Bob can successfully extract the fingerprints, where is given in (8), and if , Alice can invisibly and reliably fingerprint all flows in a time interval of length , and Bob can successfully extract the fingerprints. ∎

In Scenario 2, we assumed that all flows observed by Bob are also observed by Alice and chosen for fingerprinting (). Although this is applicable in many schemes, we present results for the case where this assumption is relaxed in Section VI, i.e., Bob observes flows with and without fingerprints.

V Extension to arbitrary rates

In this section, we extend Theorems 1 and 2 to the case that the flow rates are arbitrary.

V-a Scenario 3: All flows are fingerprinted and flow rates are arbitrary, Setting 1

Consider Scenario 3, which is the extension of Scenario 1 to arbitrary rates: Alice fingerprints all of the flows she observes (), and Bob observes only the fingerprinted flows (). We consider Setting 1 (see Fig. 0(a)), i.e., parallel queues with multiple inputs and outputs, where each queue is shared between a flow from Alice to Bob (main flow) as well as other interfering flows independent of the main flow. Here the flows rates can be arbitrary, and the main flow passing through the queue () has the rate of . Alice fingerprints the input flows of the network in the time interval , and Bob extracts the fingerprints from the flows on the output links of the network to infer the connections between input and output flows.

Similar to Scenario 1, for each flow Alice selects a codeword (fingerprint) from her codebook and embeds it in the flow by changing the packet timings of the flow. She builds her codebook based on the minimum rate of the flows , and to embed a fingerprint (of rate ) in a flow of rate , she scales the fingerprint by a factor of to obtain a modified fingerprint of rate , and then embeds it in the flow. In addition, she uses a two-phase (buffering-fingerprinting) scheme similar to those of Scenarios 1 and 2.

We calculate the number of flows () that Alice and Bob can trace by fingerprinting using this scheme, asymptotically as a function of .

Theorem 3.1.

Consider Setting 1 (see Fig. 0(a)). If Alice fingerprints all input flows () whose rates are arbitrary and Bob observes only the set of fingerprinted flows (), then Alice and Bob can invisibly and reliably trace flows in a time interval of length .

Construction: Per above, Alice employs a two-phase scheme: a buffering phase of length and a fingerprinting phase of length (see Fig. 3), where and are given in  (1) and (2). The codebook construction is similar to Scenario 1, but the rate of the fingerprints (codewords) is . To embed a fingerprint in a flow of rate , Alice selects a fingerprint and scales by a factor to generate a modified fingerprint of rate , . Since fingerprints are instantiations of a Poisson process of parameter (i.e., its inter-arrival times are instantiations of an exponential random variable of mean ), the modified fingerprint is an instantiation of a Poisson process of parameters . Next, Alice applies the inter-packet delays given by the modified fingerprint to each flow.

Recall that Bob knows the rate of each flow. Upon observing , the flow with packet timings and rate , Bob seeks to answer the following question:

Question 1: Given that Alice used the codebook whose fingerprints are of rate , what is the index of the fingerprint that was selected by Alice, scaled to rate , and transmitted through to produce the output packet timings ?

Analysis: (Invisibility) Similar to Scenario 1, we analyze the invisibility of the first and second phases separately. In the first phase, Alice slows down each flow of rate to rate . Using arguments similar to that of Theorem 1, we can show that [28, Theorem 2]:

 P(w)e>12−ϵ,

where is Willie’s error probability. Thus, this phase is invisible to Willie. In the second phase, since Alice embeds a modified fingerprint of rate in a flow of rate , the traffic pattern remains Poisson with rate indistinguishable from the pattern that Willie expects to observe. Hence, the scheme is invisible.

(Reliability) Similar to the reliability analysis in Scenario 1, we upper bound by , for all .

Recall that upon observing , Bob seeks the answer to Question 1. Note that the answer to this question is the same as the answer to the following question:

Question 2: Given that Alice used the codebook what is the index of the fingerprint that was selected by Alice and transmitted through to produce the output packet timings ?

In other words, although Alice generates a codebook whose fingerprints are of rate and then scales each fingerprint to adjust to rate of the flow, Bob’s decoding of each flow is equivalent to the case where Alice uses a codebook whose fingerprints are of rate and she does not scale the fingerprints; the only differences are in the number of fingerprints (codewords) and the time to transmit the fingerprint, as we will explain later. Therefore, from (6), Bob can successfully extract the fingerprint from the flow of rate as long as is large and

 logmT(i)2<λilog((μi−λ′i)/λi), (34)

where is the time of the transmission of the fingerprint embedded in the flow of rate . Therefore,

 logmT2<λminlog((μi−λ′i)/λi). (35)

Since the size of the codebook is , fingerprinting the flow corresponds to transmission of nats of information through the inter-packet delays of the flow . Note that scaling a fingerprint of rate to rate results in transmission of nats of information at a higher rate but a shorter time.

Since (35) holds for all , we require

 logmT2

where

 C′=λminmini{log((μi−λ′i)/λi)}, (37)

to achieve for each flow. Note that (2) implies that as . Therefore,

 Pf2→0 as T→∞. (38)

Now, consider . In the second phase, on each link Alice receives and transmits the packets according to two independent Poisson processes of equal rate. Thus, we employ a random walk analysis similar to that of Scenario 1 to show that

 Pf1≤1−erf(ϵ2√T12mT2)≤ζ as T→∞. (39)

Consequently, by (4), (38) and (39), for all , and thus Alice and Bob’s fingerprinting is reliable.

(Number of flows) The analysis is similar to that of Scenario 1. As , we require

 logmT2=(1+mα)logmT

which we can achieve as long as

 m=12min{α−1(TC′W(TC′)−1),TC′W(TC′)}, (41)

Since for , , Alice and Bob can invisibly and reliably break the anonymity of a network (Setting 1 shown in Fig. 0(a)) with flows. ∎

V-B Scenario 4: Alice fingerprints a subset of the flows, Setting 1

Consider Scenario 4, which is the extension of Scenario 2 to arbitrary rates: Alice fingerprints a subset of the flows, and is unknown to Willie. Similar to Scenario 2, since Willie has to investigate a large set of flows to detect if some are slowed down in the first phase as required for fingerprinting, Alice can make more fingerprinted flows invisible.

For each flow in , she selects a unique fingerprint from her codebook and alters the timings of that flow according to the fingerprint. We consider Setting 1 (see Fig. 0(a)), i.e., parallel queues with multiple inputs and outputs, where each queue is shared between a flow from Alice to Bob (main flow) as well as other interfering flows independent of the main flow. Flows rates are , which can be arbitrary, and the main flow passing through the queue () has the rate of . Alice fingerprints the input flows of the network in the time interval , and Bob extracts the fingerprints from the flows on the output links of the network to infer the connections between input and output flows.

For each selected flow Alice selects a codeword from her codebook and embeds it in the flow by changing its packet timings according to the selected fingerprint. Since flow rates are arbitrary, similar to Scenario 3, she builds her codebook based on the minimum rate of the flows to be fingerprinted and scales each fingerprint based on the rate of the flow to be fingerprinted. Also, she uses a two-phase (buffering-fingerprinting) scheme.

We calculate the number of flows () in which Alice fingerprints using this scheme, asymptotically as a function of .

Theorem 3.2.

Consider Setting 1 (see Fig. 0(a)). In a set containing flows with rates , if Bob observes only the fingerprinted flows (), Alice and Bob can invisibly and reliably trace flows in a time interval of length , where is given in (18), where is replaced with which is given in (37).

The construction and analysis follow from those of Scenarios 2 with modifications due to arbitrary rates. The extension to arbitrary rates follows from that of Scenario 3. ∎

Vi Mixing flows with and without fingerprints

We have previously assumed that Bob only observes the set of fingerprinted flows, i.e., . But, in practice Bob might observe a set of flows in which some of the flows are not fingerprinted, and therefore, he must be able to detect if a flow contains a fingerprint. In this Section, we consider Setting 2 (see Fig. 0(b)) and we present Scenarios 5 and 6 which are extensions of Scenarios 1 and 2, respectively, to the case where Bob observes a set of flows in which some of them are not fingerprinted. We present a detector for Bob that is able to detect if a flow is fingerprinted.

Vi-a Scenario 5: All flows are fingerprinted and Bob observes flows with and without fingerprints, Setting 2

Consider Scenario 5, which is the extension of Scenario 1 to the case where Bob observes flows with and without fingerprints (): Alice fingerprints all of the flows she observes (), flow rates are equal (), and Bob observes flows with and without fingerprints. We consider Setting 2 (see Fig. 0(b)), i.e., parallel queues with single input and output. Alice fingerprints the input flows of the network in the time interval , and Bob extracts the fingerprints from the flows on the output links of the network to infer the connections between input and output flows.

In contrast to Scenarios 1-4, Bob uses a detector which is able to distinguish whether a flow is fingerprinted. We calculate the number of flows () that Alice and Bob can trace by fingerprinting using this scheme, asymptotically as a function of .

Theorem 4.1.

Consider Setting 2 (see Fig. 0(b)). If Alice fingerprints all input flows () whose rates are equal () and Bob observes a set of flows with and without fingerprints (), then Alice and Bob can invisibly and reliably trace flows in a time interval of length .

Construction: The only difference between the construction of Scenarios 1 and 5 is that, for Scenario 5, Bob must use a detector which detects if a flow contains a fingerprint.

Here, Bob’s decoder is different from the maximum likelihood decoder proposed in [32, p. 9], which for each codeword calculates the service times that yield , removes the codewords that result in negative values of service times, and finally finds a unique codeword that corresponds to the minimum sum of service times. Instead, Bob’s decoder selects a threshold , applies a function on each codeword, and finds a unique codeword that generates an output for the function that is larger than .

Next, we describe Bob’s decoder in detail [34, p. 12]. For and , if is the sequence of packet timings before the flow passes through (inter-arrival times), then the pdf of the observed packet timings (inter-departure times) is:

 P(¯y|¯x)=eμ−λ(y0)n∏k=1(yk−wk),

where is the exponential pdf with mean , and is the waiting time, the amount of time that the queue waits until it receives the packet. Since the packet timings of the fingerprinted flow is an instantiation of a Poisson process of rate , the joint pdf of the inter-arrival times is . Consequently, the pdf of is:

 P(¯y) =∫Rn+P(¯y|¯x)n∏k=1eλ(xk)d¯x. (42)

Bob’s decoder finds a unique fingerprint (codeword) from that satisfies ; if such a unique codeword does not exist, it outputs flow not fingerprinted.

Analysis: The analysis follows from that of Scenario 1. The only differences appear in the analysis of Bob’s decoding error probability. The auxiliary threshold decoder used in the analysis of the mismatched decoder in [34, p. 413-417] provides what we need for our application. If Bob uses this detector, the decoding error probability of a fingerprinted flow will be:

 Pf2→0 as T→∞, (43)

which implies that if we generate independent instantiations of a Poisson process of rate on a time interval of length , , we select one of them and send a packet stream whose packet timings follow over the network, then the probability that at least one satisfies tends to zero, i.e.,

 P(∃Wk≠l:P(¯y|Wk)/P(¯y)>β|Wl sent )→0 as T→∞. (44)

Consider the case where Bob observes a flow that is not fingerprinted. Recall that the packet timings of all the flows follow a Poisson process of rate . Denote by an instantiation of a Poisson process that corresponds to the packet timings of the this flow before it passes through the network. If Bob detects a fingerprint, it must be that one of the fingerprints in the codebook resulted in . Hence,

 Pf3=P(∃Wk:P(¯y|Wk)P(¯y)>β∣∣∣Z⋆ sent ) (45)

Recalling that and are independent instantiations of a Poisson process of rate , (43) and (44) yield as . Thus, Alice and Bob’s fingerprinting is reliable. ∎

Vi-B Scenario 6: Alice fingerprints a subset of the flows and Bob observes flows with and without fingerprints, Setting 2

Consider Scenario 6, which is the extension of Scenario 2 to the case where Bob observes flows with and without fingerprints (): Alice fingerprints a subset of the flows she observes (), flow rates are equal (), and Bob observes flows with and without fingerprints. We consider Setting 2 (see Fig. 0(b)), i.e., parallel queues with single input and output. Alice fingerprints the input flows of the network in the time interval , and Bob extracts the fingerprints from the flows on the output links of the network to infer the connections between input and output flows.

Similar to Scenario 5, Bob’s detector is able to distinguish whether a flow is fingerprinted. We calculate the number of flows () that Alice and Bob can trace by fingerprinting, asymptotically as a function of .

Theorem 4.2.

Consider Setting 2 (see Fig. 0(b)). In a set containing flows with equal rates (), if Bob observes flows with and without fingerprints (), Alice and Bob can invisibly and reliably trace flows in a time interval of length , where is given in (18), where is replaced with

 C′′=λlog(mini{μi}/λ), (46)

Note that the replacement of with


text:
# Energy created by falling object

1. Dec 20, 2005

### Greg E

If there is a 1.36 kg weight falling .1524 meters,
how many joules are created when the object reachs the end of the .1524 meters. How do you calculate this?
I came up with 2.032 joules which is .20723 kg meters which I think is enough power to lift 1.36 kg .1524 meters which is the same as where I started and that cannot be correct because a falling object has more power than the same object standing still.
Thanks,
Greg

2. Dec 20, 2005

### Astronuc

Staff Emeritus
This seems like a homework problem from Introductory Physics.

However, an object falling implies falling due to gravity. What one has is a conversion/transformation from gravitational potential energy to kinetic energy.

Taking the acceleration of gravity to be constant, the change in gravitational potential energy is mg$\Delta h$, where $\Delta h$ is the change in elevation.


text:
# ER-301/Teletype Integration

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

## Required Hardware Connections

1. First determine your ER-301 board revision.
2. If you have an ER-301 with board revision 7 (i.e. ER-301 manufactured before June 2018), then please go here.
3. Otherwise go here.

## Status

As of v0.3.06 of the ER-301 firmware, there is support for Teletype to control the ER-301 over the i2c bus. There is a discussion thread over on the forum dedicated to this topic:

## Available Units and Commands

 ER-301/Teletype integration requires ER-301 firmware v0.3.06 or later, and Teletype firmware v2.3 or later (discussion and github branch linked here).

The following commands are available on the Teletype for control of the ER-301. In all cases, the first parameter is the port number which can take any value from 1 to 100.

Command Description
SC.TR port α Set TR value to α (0/1)
SC.TR.TOG port Toggle TR
SC.TR.PULSE port Pulse TR using TO.TR.TIME/S/M as an interval
SC.TR.TIME port α time for TR.PULSE; α in milliseconds
SC.TR.POL port α polarity for TO.TR.PULSE set to α (0-1)
SC.CV port α CV target α (bipolar)
SC.CV.SLEW port α CV slew time; α in milliseconds
SC.CV.SET port α set CV to α (bipolar); ignoring SLEW
SC.CV.OFF port α CV offset; α added at final stage

(Adapted from: TELEX Command Reference by bpcmusic)

The above SC.TR and SC.CV Teletype commands are paired with two corresponding units on the ER-301 of the same name:

### SC.TR Unit

The SC.TR unit has a single parameter called 'port' which is also modulate-able. This port parameter matches the first argument of all of the SC.TR commands on the Teletype side. If desired, you can have multiple units set to the same port.

For example, the following Teletype command:

SC.TR.PULSE 42

will cause all instances of SC.TR units with port equal to 42 to output a pulse. Bang!

### SC.CV Unit

The SC.CV unit has a single parameter called 'port' which is also modulate-able. This port parameter matches the first argument of all of the SC.CV commands on the Teletype side. If desired, you can have multiple units set to the same port.

For example, any of the following Teletype commands:

SC.CV 42 N 12
SC.CV 42 V 1
SC.CV 42 VV 100
SC.CV 42 1638

will cause all instances of SC.TR units with port equal to 42 to slew to the value of 0.1 (which corresponds to the external value of 1V).

#### Value conversions

The Teletype maps the integers -16384 to 16384 (*) to the output voltages -10V to 10V. Since the ER-301, maps the voltages -10V to 10V to the internal values of -1 to 1, ER-301 values are calculated from Teletype raw values like this:

$\displaystyle \mbox{Value in ER-301} = \frac{\mbox{Value in Teletype}}{16384}$

(*) $\displaystyle 16384 = 2^{14}$

### Selecting Slices

Two points to consider when using SC.CV and SC.TR commands to select and trigger slices on the ER-301 (or any device that uses a CV/gate selection mechanism).

#### Slew

Make sure the CV slew is set to zero (SC.CV.SLEW port 0), or, use the SC.CV.SET command instead of the SC.CV command. The SC.CV.SET command ignores the slew setting.

#### Ordering

Place your SC.TR commands after the SC.CV/SC.CV.SET commands in your Teletype script. At the moment, Teletype I2C messages are sent one-by-one and there is no grouping functionality (i.e. here is a bunch of messages to treat as simultaneous). So the order in which your Teletype program generates the messages is the order in which the ER-301 will receive them along with a non-deterministic time interval between the messages (especially if there are a number of devices sharing the i2c bus).

## Configuring the ER-301

You can enable Teletype i2c communication by navigating to Admin > System Settings > Monome Teletype and choosing the appropriate settings:

You can also set the ER-301 slave address in this same screen. If you have one ER-301, then use 0x31. Use 0x32 for your second ER-301 and use 0x33 for your third (!) ER-301. This way the Teletype will automatically route your commands in the following manner:

• ports 1-100 to the first ER-301 (0x31),
• ports 101-200 to the second ER-301 (0x32), and,
• ports 201-300 to the third ER-301 (0x33).
 If you are using older ER-301 firmware (prior to v0.4), you might see i2c addresses starting with 0xB. These addresses conflict with other devices. Please stick with the 0x3 addresses.


text:
# Steiner's Calculus Problem

## Theorem

Let $f: \R_{>0} \to \R$ be the real function defined as:

$\forall x \in \R_{>0}: \map f x = x^{1/x}$

Then $\map f x$ reaches its maximum at $x = e$ where $e$ is Euler's number .

## Source of Name

This entry was named for Jakob Steiner.