Tuesday, December 12, 2017

Listening to Wi-Fi probe requests

Most Wi-Fi capable devices broadcast probe requests to figure out what networks are available in the area. When an access point receives a probe request it will answer with information about the network it is running. The probe request contains the device's MAC address, which is usually static, so by listening to the probe requests you can determine if a specific device is in the vicinity of your Wi-Fi receiver. How often probe requests are sent is device specific but most devices send them every now and then, even when they are already connected to a network.

To listen to the probe requests perform the following steps. Note that not all Wi-Fi cards allow you to see the probe requests. If you are not seeing any probe requests it's probably because your Wi-Fi card hides them. I'm using a "D-Link DWA-111 Wireless G USB Adapter" on Windows.
  1. Install python 3.6.3 (https://www.python.org/downloads/)
  2. Download my script from here
  3. Install Npcap 0.94 (https://nmap.org/npcap/). Make sure you click "Support raw 802.11 traffic (and monitor mode) for wireless adapters" during installation. I had to re-boot my computer after the installation to get everything to work well.
  4. Install Wireshark 2.4.2 (https://www.wireshark.org/#download)
  5. Set the Wi-Fi card to monitoring mode by running the following command as administrator. "Wi-Fi 2" is the interface name and should be changed to whatever interface you wish to use for the sniffing.

    C:\Windows\System32\Npcap\WlanHelper.exe "Wi-Fi 2" mode monitor
  6. Run my script. You may have to change the interface name and tshark path.

    python wifi_monitor.py "Wi-Fi 2" "C:\Program Files\Wireshark\tshark.exe"

    If everything works you should now see the MAC addresses of devices doing probe requests in your vicinity, something like this:

    Date, Time, Number of previous sightings, Is local address?, MAC address
    Local addresses are usually not static over time!
    2017-11-06 21:13   6312   f4:f5:d8:ff:e0:b9
    2017-11-06 21:17      0 X 72:a3:98:af:12:c3
    2017-11-06 21:17    200  
    70:70:0d:ce:21:77
    2017-11-06 21:20    201  
    70:70:0d:ce:21:77
The MAC addresses are a bit hard to remember so you can create aliases for them by adding a line in aliases.txt.

70:70:0d:ce:21:77 Suspicious device

70:70:0d:ce:21:77 will now show up as Suspicious device in the script output. Note that it may take a while before the script re-loads aliases.txt and the change takes effect.

The script saves all the probe requests in log.txt. I have implemented a few scripts that extract statistics from the log file. histogram_of_sighting_times.py creates a histogram of the sighting times for a device.

python histogram_of_sighting_times.py 1 4 12 "Suspicious device"


The script uses Matplotlib so you need to install that before using it (https://matplotlib.org/users/installing.html).

device_graph.py creates a device graph based on how well device sightings correlate temporally. If two devices always show up at the same time they will have a very strong connection in the graph, if two devices have never appeared close to each other in time they will have no connection at all. The created graph (device_graph.gdf) can be analyzed in Gephi (https://gephi.org/) or any similar program. For more information about Gephi check out this post.

Thursday, December 7, 2017

Roboreader

Edited 20180121

Staying aware of what's going on around you in a large software project is a bit of a chore. Meetings, reading various information sources like mail lists and wikis, maintaining queries and watches in support systems like gerrit, and so on. It would be nice if this could be automated, at least to some extent, so I gave it a try.

Roboreader continuously fetches new texts from various sources, reads them, and shows you only the texts that you are interested in. Currently it supports two sources, imap (email) and gerrit, but it's easy to add more sources. To figure out which texts that are of interest to you there are four match engines.

Pattern search
This match engine just applies a number of regular expressions you have created to the texts. If a text matches any of the regular expressions it is considered interesting.

Word frequency
This match engine figures out your interests by looking at which words you overuse. It looks at all the mails, patches, bug reports, etc that you have written and compares them to all the mails, patches, bug reports, etc that other people have written. If you overuse for example "anti-banding" it will assume you are interested in that topic and all texts containing "anti-banding" will be marked as interesting to you.

ANN
This match engine uses an ANN (artificial neural network) classifier to classify texts as "interesting" or "not interesting". The training data for the "interesting" class are the texts you have authored and the training data for the "not interesting" class are the texts that other people have authored. During training the ANN will learn patterns that are unique to you and use them to figure out which texts you might be interested in. Much like the "word frequency" match engine, but patterns instead of words, which makes this match engine a lot more flexible.

Carrot2
This match engine uses the open-source text clustering engine Carrot2. It clusters all new texts and all the texts you have authored. If a new text ends up in the same cluster as one of the texts you have authored it is considered interesting.

I am currently not working with large scale software development so I couldn't test how well it all worked myself, instead I set it loose on AOSP's (Android) gerrit and told it I was "Jakub Pawlowski", a software engineer at Google working with bluetooth. This approach is a bit flawed. All the texts are patches, which is unlikely in a real scenario. It is also hard for me to assess whether the found texts are of interest to Jakub or not as I'm not Jakub. Better than nothing though.

The results where a bit so-so. Pattern search works as expected but since you have to write the regular expressions yourself it doesn't add much value. Word frequency and ANN find interesting texts without too much noise, but I've got a feeling they miss a lot of interesting texts. I was unable to get anything useful out of Carrot2, way too much noise or no matches at all, could be a configuration issue though.

If you want to try it out yourself you can download the script here. To get going just edit config.xml and run the script. Current directory is used when looking for or storing files (like configuration and state).

python3 roboreader.py

Monday, August 28, 2017

Simulating the biological brain

Like many people I'm interested to know how a biological brain learns. After some light Internet searching I reached the conclusion that nobody really knows. The one thing that has some experimental support is Hebbian theory but the consensus appears to be that this theory alone can not explain the learning process. Commonly suggested additions are reinforcement and noise.

By combining Hebbian theory, reinforcement, and noise you can actually create something that possibly could work, but surprisingly I could not find anyone that had attempted it. Probably because every one that has tried have failed, and their work have therefore not reached any wider audience. Being overly curious I decided to try it out myself. Unfortunately I also failed to achieve any significant learning but if you want to know a bit more about how I put it all together then just keep reading. The code is available here in case you want to see exactly how I implemented something.

The neurons in my artificial brain are based on the typical Hebbian theory neurons and stabilized by forcing the sum of the weights to equal one. The learning rate is derived from "reinforcement / average_reinforcement". The idea is that the neurons shall learn when the network is performing better than normally.

I added a non-traditional feature to the neurons where a weight that is lower than x becomes negative when calculating the neuron output. The reason for this is that I think the biological brain has some sort of negative weight construction. Without negative weights all neurons would trigger on an all one input. If this was the case we would see everything when looking at the sun, which does not happen (for me at least).

The noise is not as random as one might think. The neuron controls both the characteristics and timing of the noise. The timing is particularly interesting. A neuron needs to identify when it is under-performing relative to the rest of the network, and at that time re-purpose itself by applying noise to its weights. My neurons use the following five rules when deciding if it is time to apply noise or not.
  1. If the reinforcement is low the noise probability shall be high and vice versa. If things aren't going well we need to take more risks trying to find a way forward. If things are going well we don't want to risk ruining our well functioning network.
  2. If the neuron is primarily triggering when the reinforcement is higher than normally then the neuron is over-performing so the noise probability for that neuron shall be lower, and vice versa.
  3. If the neuron has not applied noise for a long time the probability for it applying noise shall be reduced. We don't want to destroy something that has worked well for a long time.
  4. If no one is picking up the neuron's output there is no interest for the pattern this neuron is detecting, so the neuron shall be re-purposed.
  5. If a neuron is constantly or never triggering it is not adding anything to the network and shall therefore be re-purposed.
In my artificial brain the reinforcement signal is created by some python code that I've written. In a biological brain I imagine the reinforcement signal is produced by a hard-wired part of the brain which has been designed by evolution.

I've tried to make sure that everything is compatible with the biological brain. The averages are for example approximations in one variable as storing long histories is probably difficult for a biological neuron.

For the simulation I used a slightly modified version of the environment from my previous reinforcement experiment (post). There are two circles, one moves randomly and the other is controlled by the artificial brain. The goal is to keep the two circles as close as possible. The artificial brain had 24+4 neurons in a 2-layer feed-forward configuration.

To have any chance of getting this working it all needs to be carefully tuned. There are 58 tunable variables and they where tuned using stochastic hill climbing.

After training for 100000 iterations (the video is 1000 iterations long) the behavior of the artificial brain looks as follows.


Not particularly impressive. Looks like the secrets of the biological brain are safe, for now.

20210502: I revisited this project and fixed some minor issues, scaled up both the size of the network and the tuning time (to ~6 months), but still no success. The new code can be found here.

Thursday, April 20, 2017

How large is the online drug market?

I think people buy bitcoins for primarily two reasons.
  1. To be able to by drugs online
  2. Speculation, thinking that the bitcoin value will be higher at some point in the future
Drug buyers probably make significantly smaller purchases of bitcoins than speculators. If this is true one can work out the intent of the bitcoin purchase (speculation or buying drugs) by looking at the size of the purchase.

Transaction logs from many bitcoin markets can be found at http://api.bitcoincharts.com/v1/csv/.


If we assume that bitcoin purchases smaller than or equal to 199USD are for buying drugs and purchases larger than 199USD are for speculation we get the following diagram.


2016 drugs for 512 million USD where bought through the USD->bitcoin->drugs path.

The over 1000% increase in drug purchases between 2012 and 2013 looks a bit suspicious. Can the market really grow that fast? Maybe there is some speculation, which can grow much faster than the drug market, going on in the <=199USD range. Automated speculation could operate in that range, but would be discouraged from doing so by rising transaction fee costs. Unfortunately the huge volume difference between the speculators and the drug buyers means that not many percent of the speculation volume needs to end up in the <=199USD range to severely corrupt my estimate of the online drug market size.

The previous model does not include drug purchases larger than 199USD, and there are likely quite a few of those. If we assume there was only drug trade and no speculation in 2012 we can use the 2012 transaction size distribution as a template for the "buying drugs" class.  This assumption is not completely crazy, in 2012 Silk Road had been online for almost a year so the drug trade was going on but bitcoin was not yet very well known so speculation was hopefully minimal. Fitting 2012's transaction size distribution onto 2016 looks as follows. The area under the green line is the drug trade, the rest is speculation.


The result of this model looks as follows.


2 billion USD 2016. Almost three times as much money is spent on drug purchases >199USD than purchases <=199USD. The most common bitcoin market transaction size for drug buyers is 500USD. There needs to be quite a lot of larger drug purchases for this to make sense, or there was more speculation in 2012 than I thought.

The huge increase between 2012 and 2013 is seen in this model also, which is expected as the fitting algorithm makes the same assumption as the previous model, that there is no speculation in the <=199USD range. If there is significant speculation in the <=199USD range the output of this model will be just as corrupt as the previous one.

People in the US spend ~100 billion USD on drugs every year (source) so 0.5-2% of the drugs pass through the online markets, if my numbers are correct.

RAND have also tried to estimate the size of the online drug market but with a different approach where they crawled some of the larger marketplaces for drugs and tried to get the information from the collected data (details). They got a worldwide yearly revenue of 253-300 million USD.

The big difference between my estimate and RAND's estimate is another indicator that there is significant speculation in the <=199USD range, probably from speculation bots, as proposed earlier. This makes my method a lot less reliable.

The script that generated all the diagrams can be found here.

Wednesday, March 29, 2017

Tap input

I thought it would be nice if you could do some basic things on the phone without getting it out of your pocket. Things like skipping to the next song, starting and stopping the music, getting the current time, etc. I have written an Android app that lets you do exactly this. The app listens to the accelerometer and detects when you tap the exterior of the phone with your finger. Double, triple, and 4-taps can be bound to different actions, like skipping to the next track. Get the app here.

Thursday, March 9, 2017

Konsultkalkylator

Slidereglagen fungerar dåligt på mobilversionen. Bloggers funktion för att swipa mellan inlägg snor inputten. Det går fortfarande att klicka på slidereglagen, eller kan man byta till webbversionen (länk längst ner på sidan).

Bruttolön
Semester
Semestertillägg
Arbetstidsförkortning
Allmän övertid
Ersättning för allmän övertid
Kvalificerad övertid
Ersättning för kvalificerad övertid
Övriga icke-fakturerade arbetsdagar
Revision, försäkringar, kontor, m.m
Mellanhand
Tjänstepension (ITP-1)


Tuesday, February 14, 2017

Reinforcement learning

Code and the trained network can be found here.

To gain a deeper understanding of reinforcement learning I decided to write my own implementation.

I made my own environment (or game if you like). There are two circles. Each circle has a force acting on it. By controlling the direction of the force you can control the movement of the circle. One circle moves randomly and the other is controlled by the player. The goal is for the player to keep his circle as close as possible to the randomly moving circle.

I use a fully connected two layer network. The inputs are, target position, target velocity, player position, and player velocity. The first layer contains 160 neurons and is supposed to re-arrange the input to make it available via a present/not present approach rather than a parse strength approach, which is more difficult for neurons. This is done by having different neurons activate at different input strengths. By doing something like "neuron A but not neuron B" the second layer can get a specific input's strength.

The second layer contains 100 neurons and is supposed to identify environment states. Notice that we are not talking about exact states, could be something like, if the target is in this area and I'm in this area.

The output of the second layer is used to populate 32 classes. The classes are then turned into probabilities with softmax. Each class represents a specific force angle.

The loss function is a standard mean cross entropy construction.

The training contains three steps which are repeated till no more progress is made.
  1. Ten sessions/games are executed. At every frame the network is feed the current state and produces a probability for each output class. A random action (force angle) is chosen with the probability distribution returned from the network. So if the network has assign equal probability to all classes (the network is unsure of what to do) the action will be truly random, if the network is 70% sure class 4 should be used then class 4 will be used in 70% of the cases, if the network is 100% sure class 6 should be used then class 6 will definitely be used.
  2. Training data for the network is constructed from the states and actions in the best performing session.
  3. Seven network training steps are performed to increase the probabilities for the actions taken in the most successful session.
State-action pairs that are often in the winning session will be assigned higher probabilities. Higher probabilities means less exploration in those cases, so after a while it becomes likely that all the basic moves are in all sessions. At this point becoming the winning sessions is all about fine tuning the basic moves. This entire thing is repeated endlessly with ever finer fine tuning.

State-action pairs can contradict each other and this is how all the bad state-action pairs in the winning sessions are "removed". The bad state-action pairs in one iteration cancels out the bad state-action pairs in another iteration.

This is what it looks like before training



... and this is after a night of training

Tuesday, January 3, 2017

An app that makes mirroring your phone's display on the TV a bit more useful

I got a Chromecast for Christmas and with it I can mirror my phone's display on the TV, without any wires. It works pretty well, good quality and not much lag. Using the TV as a display for the phone is appealing as phones have small displays. There is one annoying thing though. Every time you need to click on something, like a web page link, you have to look down at the phone.

To get rid of a lot of these display changes I wrote an app that lets you see where your fingers are on the display. If you swipe in from the edge of the display the app will capture the input and use it to draw your finger's position. You can now easily place your finger correctly without looking at the phone as the finger's current position is visible on the TV. To execute the click you just lift the finger and put it down again at the same position. The whole thing works surprisingly well. You can download the app here and try it out yourself.