Sunday, July 23, 2023

The final piece of the puzzle

The sweat on your face,
A sign of hard work,
Is finally getting colder.

The fever you felt,
It was a mark
Of the upcoming game over.

It took a while
To see the truth,
You finally see the impalpable.

I mean that part,
Which drove you mad,
The final piece of the puzzle.

Thursday, September 8, 2022

The verse of the innevitable ...

The chapter is closed and as it turns,
The chapter has many pages.
What was recorded, the things you deserve,
Will stay in the book for ages.

The words in those pages, they will reveal
The happy, the struggle, the challenge.
The way it was handled, the power of will
Sometimes, the lack of courage.

The letters, in opening, start like a breeze,
Then the gusts get stronger and stronger.
The ending is like the calm of the seas
When the hurricane is over.

Monday, April 12, 2021

Golden ratio, Fibonacci numbers and ... another sequence

Over the last weekend, another question was asked and later disappeared on/from Math StakExchange. The sequence, from that question, is too nice to "let it go", thus, copy/pasting my answer here.

Let's define the following sequence $$a(n)=\left\lfloor n\cdot\phi + \frac{1}{2}\right\rfloor$$ where $\phi$ is the golden ratio. Is there a closed form for the following sequence $$a^{\circ k}(n)=\underbrace{a(((...a(n)...)))}_{k \text{ times}}$$?

Calculating a few values of the sequence reveals that this is the A007067, with the property that $$a(a(n))=a(n)+n \tag{1}$$ a result proved in 2006. Let's show it ...


Proposition 1. $\left\lfloor \frac{a(n)}{\phi} + \frac{1}{2}\right\rfloor=n$

Given $x-1 < \lfloor x\rfloor \leq x$, we have $$n\phi - \frac{1}{2} < a(n)\leq n\phi + \frac{1}{2} \iff \\ n-\frac{1}{2\phi} < \frac{a(n)}{\phi}\leq n+\frac{1}{2\phi} \iff \\ n+\frac{1}{2}-\frac{1}{2\phi} < \frac{a(n)}{\phi}+\frac{1}{2}\leq n+\frac{1}{2}+\frac{1}{2\phi}$$

Given $1+\frac{1}{\phi}=\phi$ and $\frac{1}{2}-\frac{1}{2\phi} > 0$, then $$n < n+\frac{1}{2}-\frac{1}{2\phi} < \frac{a(n)}{\phi}+\frac{1}{2}\leq n+\frac{\phi}{2} < n+1$$

or $$n < \frac{a(n)}{\phi}+\frac{1}{2} < n+1 \Rightarrow \left\lfloor \frac{a(n)}{\phi} + \frac{1}{2}\right\rfloor=n$$


Proposition 2. $a(a(n))=a(n)+n$.

Obviously $a(n)\in\mathbb{N}$, then $$a(a(n))= \left\lfloor a(n)\cdot\phi + \frac{1}{2}\right\rfloor= \left\lfloor a(n)\cdot\left(1+\frac{1}{\phi}\right) + \frac{1}{2}\right\rfloor=\\ a(n)+\left\lfloor \frac{a(n)}{\phi} + \frac{1}{2}\right\rfloor = ...$$

applying Proposition 1 $$...= a(n)+n$$


Now back to the original question, a few observations, using $(1)$ $$a^{\circ 2}(n)=a(a(n))=F_2\cdot a(n) + F_1\cdot n$$ $$a^{\circ 3}(n)=a(a(\color{red}{a(n)}))=a(\color{red}{a(n)})+\color{red}{a(n)}=\\ 2\cdot a(n)+n=F_3\cdot a(n) + F_2\cdot n$$ $$a^{\circ 4}(n)=a(a(a(\color{blue}{a(n)})))=2\cdot a(\color{blue}{a(n)})+\color{blue}{a(n)}=\\ 3\cdot a(n)+2n=F_4\cdot a(n) + F_3\cdot n$$

It's easy to see, by induction, this is $$a^{\circ k}(n)=F_k\cdot a(n) + F_{k-1}\cdot n \tag{2}$$

because $$a^{\circ (k+1)}(n)=a^{\circ k}(a(n))=F_k\cdot a(a(n)) + F_{k-1}\cdot a(n)=\\ (F_k+F_{k-1})\cdot a(n) + F_{k}\cdot n=F_{k+1}\cdot a(n) + F_{k}\cdot n$$

Friday, November 6, 2020

An interesting trigonometric identity

Questions follow a complex life cycle on Math StackExchange. Some questions are deleted, because they don't meet the community standards. Nonetheless, some of those deleted questions are interesting and non-trivial. In this post, I will cover one of those questions (you may not be able to see it, without sufficient privilege). I spent a few good hours to spot the pattern, so it won't feel like I wasted that time :) ... and you might like the question as well.

Is it true that $$\prod\limits_{k=1}^{2^{1999}}\left(4\sin^2\left(\frac {k\pi}{2^{2000}} \right)-3\right)=-1$$?

It seems so. Given this and this identities:$$\color{red}{\prod\limits_{k=1}^{2^{1999}}\left(4\sin^2\left(\frac {k\pi}{2^{2000}} \right)-3\right)}= \prod\limits_{k=1}^{2^{1999}} \left(\left(2-2\cos{\frac{k\pi}{2^{1999}}} \right)-3\right)=\\ \prod\limits_{k=1}^{2^{1999}} \left(-1-2\cos{\frac{k\pi}{2^{1999}}} \right)= \prod\limits_{k=1}^{2^{1999}} \left(1+2\cos{\frac{k\pi}{2^{1999}}} \right)=\\ -\prod\limits_{k=1}^{2^{1999}-1} \left(1+2\cos{\frac{k\pi}{2^{1999}}} \right)=\\ -\prod\limits_{k=1}^{2^{1998}-1} \left(1+2\cos{\frac{k\pi}{2^{1999}}} \right) \cdot 1 \cdot \prod\limits_{k=2^{1998}+1}^{2^{1999}-1} \left(1+2\cos{\frac{k\pi}{2^{1999}}} \right)=\\ -\prod\limits_{k=1}^{2^{1998}-1} \left(1+2\cos{\frac{k\pi}{2^{1999}}} \right) \cdot\prod\limits_{k=1}^{2^{1998}-1} \left(1+2\cos{\frac{\left(2^{1998}+k\right)\pi}{2^{1999}}} \right)=\\ -\prod\limits_{k=1}^{2^{1998}-1} \left(1+2\cos{\frac{k\pi}{2^{1999}}} \right) \cdot\prod\limits_{k=1}^{2^{1998}-1} \left(1+2\cos{\left(\frac{\pi}{2}+\frac{k\pi}{2^{1999}}\right)} \right)=\\ -\prod\limits_{k=1}^{2^{1998}-1} \left(1+2\cos{\frac{k\pi}{2^{1999}}} \right) \cdot\prod\limits_{k=1}^{2^{1998}-1} \left(1-2\cos{\left(\frac{\pi}{2}-\frac{k\pi}{2^{1999}}\right)} \right)=\\ -\prod\limits_{k=1}^{2^{1998}-1} \left(1+2\cos{\frac{k\pi}{2^{1999}}} \right) \cdot\prod\limits_{k=1}^{2^{1998}-1} \left(1-2\cos{\frac{\left(2^{1998}-k\right)\pi}{2^{1999}}} \right)=\\ -\prod\limits_{k=1}^{2^{1998}-1} \left(1+2\cos{\frac{k\pi}{2^{1999}}} \right) \cdot\prod\limits_{k=1}^{2^{1998}-1} \left(1-2\cos{\frac{k\pi}{2^{1999}}} \right)=\\ -\prod\limits_{k=1}^{2^{1998}-1} \left(1-4\cos^2{\frac{k\pi}{2^{1999}}} \right)= -\prod\limits_{k=1}^{2^{1998}} \left(1-4\cos^2{\frac{k\pi}{2^{1999}}} \right)=\\ -\prod\limits_{k=1}^{2^{1998}} \left(1-4\left(1-\sin^2{\frac{k\pi}{2^{1999}}} \right)\right)= -\color{red}{\prod\limits_{k=1}^{2^{1998}} \left(4\sin^2{\frac{k\pi}{2^{1999}}}-3\right)}$$

By induction: $$\prod\limits_{k=1}^{2^{1999}}\left(4\sin^2\left(\frac {k\pi}{2^{2000}} \right)-3\right)= -\prod\limits_{k=1}^{2^{1998}} \left(4\sin^2{\frac{k\pi}{2^{1999}}}-3\right)=\\ (-1)^2 \prod\limits_{k=1}^{2^{1997}} \left(4\sin^2{\frac{k\pi}{2^{1998}}}-3\right)=\\ (-1)^n \prod\limits_{k=1}^{2^{1999-n}} \left(4\sin^2{\frac{k\pi}{2^{1999-n+1}}}-3\right)=\\ (-1)^{1999} \prod\limits_{k=1}^{1} \left(4\sin^2{\frac{k\pi}{2}}-3\right)=(-1)^{1999}$$

Saturday, July 25, 2020

A few words about ConcurrentHashMap, compute() method

There is one ambiguous moment in the Java documentation of the compute() method from the ConcurrentHashMap class:

Some attempted update operations on this map by other threads may be blocked while computation is in progress, so the computation should be short and simple, and must not attempt to update any other mappings of this Map.

It's not clear what is being blocked. Is it the access to the entire map or to the key? Let's find out, by conducting a few experiments with the following code:

package tests.concurrency;

import java.util.Map;
import java.util.Objects;
import java.util.concurrent.ConcurrentHashMap;

public class TestConcurrentHashMapCompute implements Runnable {
	private static final Map<Key, String> MAP = new ConcurrentHashMap<>();
	private static final int MAX_RUNS = 100;
	private static final long SLEEP_TIME = 5000;

	public static void main(String[] args) {
		Thread th1 = new Thread(new TestConcurrentHashMapCompute());
		Thread th2 = new Thread(new TestConcurrentHashMapCompute());

		th1.start();
		th2.start();
	}

	@Override
	public void run() {
		final String name = Thread.currentThread().getName();
		for (int i = 0; i < MAX_RUNS; i++) {
			final String value = MAP.compute(new Key(name), (k, v) -> {
				System.out.println(name + ": enters");
				sleep();
				System.out.println(name + ": exits");
				return name;
			});
			System.out.println(name + ": " + value);
		}
	}

	private static void sleep() {
		try {
			Thread.sleep(SLEEP_TIME);
		} catch (Exception ex) {}
	}

	private static class Key {
		private final String value;

		private Key(String value) {
			this.value = value;
		}

		@Override
		public int hashCode() {
			return 1;
			// return Objects.hash(value);
		}

		@Override
		public boolean equals(Object o) {
			if (this == o) {
				return true;
			}
			if (o == null || getClass() != o.getClass()) {
				return false;
			}
			Key other = (Key) o;
			return Objects.equals(value, other.value);
		}
	}
}

It's nothing complicated, two threads calling the compute() method of a shared ConcurrentHashMap instance, using Key class instances as the key for the map. However, pay attention to the hashCode() method inside the Key class:

		@Override
		public int hashCode() {
			return 1;
			// return Objects.hash(value);
		}

Depending on what is being returned (comment/uncomment the relevant lines), you will see different behaviour. And, by the way, return 1 is a valid hashCode() implementation, according to the Java documentation:

- If two objects are equal according to the equals() method, then calling the hashCode method on each of the two objects must produce the same integer result.
- It is not required that if two objects are unequal according to the equals() method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hash tables.

The result is:
- With return Objects.hash(value), i.e. String's descent hashCode() implementation, the threads run in parallel, as if the block was on the Key.
- With return 1, the threads run sequentially, as if the block was on the entire Map.

In fact, the block is on the bucket indexed by the Key. That's what the hashCode() method is about, to quickly access the relevant bucket. HashMap, for example, uses a singly linked list as the storage for the buckets.

Wednesday, July 3, 2019

401 and/or 403 and a short story of secure RESTful

The problem of what HTTP codes to use inevitably comes when designing RESTful services. There is a bit of subtlety, however, with regards to the 401 and 403 status codes. Here and there you will read advices suggesting to use:

  • 401 for when an access token isn’t provided, or is invalid.
  • 403 for when an access token is valid, but requires more privileges.
and people will follow these advices without considering the security part of the problem.

And the problem is that such an implementation can leak sensitive information. Here is my reply to the above mentioned article. In cryptography this is known as oracle and can lead to pretty serious attacks.

If the attacker sees a 403 status code, after a huge array of failed attempts with 401, this means that whatever the attacker tried passed the authentication phase, but failed the authorisation. Bingo, they just figured out a valid set of credentials (or tokens or ...) and your system said that in "clear text". It is similar to the "Username or password invalid" best practices (and don't read things like this!).

How to avoid the problem? Stick with one status code (e.g. 403) for both cases (failed authentication and failed authorisation), avoid being too user (or client) friendly. You can log the incident and return a unique request ID to the client. If a genuine client reports the problem, that request ID should help finding more details in logs. And of course track/monitor all the authentication/authorisation failures for anomaly detection purposes.

Now the fun part, all of the above as a mathematical proof. Let's assume a system where the maximum number of credentials possible is $N$, has $M$ registered users and $K$ of those users have access to a specific resource that the attacker tries to brute-force, $N>M\geq K$. Let's consider the following propositions/events:

  • $A$ - guess a credential by accessing the given resource.
  • $B$ - The system is designed to return: HTTP 200 for valid credentials with access to the resource, HTTP 403 for valid credentials with no access to the resource, HTTP 401 for invalid credentials. For simplicity, we can say $B=\{200\}\bigcup \{403\}\bigcup \{401\}$.
  • $C$ - The system is designed to return: HTTP 200 for valid credentials with access to the resource, HTTP 403 for valid credentials with no access to the resource or invalid credentials. Or $C=\{200\}\bigcup \{403\}$

In other words:

  • Cardinality of $A$ givnen $B$ is: $K$ possible cases of HTTP 200, plus $M-K$ possible cases of HTTP 403. Grand total is $M$.
  • Cardinality of $A$ givnen $C$ is: $K$ possible cases of HTTP 200, which is also the grand total.

Now let's compute probabilities: $$P(A \mid B)=\frac{M}{N}$$ and $$P(A \mid C)=\frac{K}{N}$$ Obviously (because $M \geq K$) $$P(A \mid B) \geq P(A \mid C)$$ which means, a system designed like $B$ gives greater chances to the attacker to guess credentials. Obviously, it doesn't matter when all the registered users have access to the resource (i.e. $K=M$). End of discussion!

P.S. The way I computed probabilities may look a bit superficial, here is another way using total probabilities or $$P(A\mid B) = \frac{P(A \cap B)}{P(B)}=\sum\limits_{C_n} \frac{P(A \cap B \cap C_n)}{P(B)}=\\ \sum\limits_{C_n} \frac{P(A \cap B \cap C_n)}{P(B\cap C_n)}\cdot \frac{P(B\cap C_n)}{P(B)}=\\ \sum\limits_{C_n} P(A \mid B \cap C_n)\cdot P(C_n\mid B)$$ Then:

  • $$P(A\mid B)=P(A\mid B \cap \{200\})\cdot P(\{200\}\mid B)+\\ P(A\mid B \cap \{403\})\cdot P(\{403\}\mid B)+\\ P(A\mid B \cap \{401\})\cdot P(\{401\}\mid B)=\\ P(A\mid \{200\})\cdot P(\{200\}\mid B)+ P(A\mid \{403\})\cdot P(\{403\}\mid B)+\\ P(A\mid \{401\})\cdot P(\{401\}\mid B)=\\ 1\cdot P(\{200\}\mid B)+ 1\cdot P(\{403\}\mid B)+ 0\cdot P(\{401\}\mid B)=\\ \frac{K}{N}+\frac{M-K}{N}=\frac{M}{N} $$
  • $$P(A\mid C)=P(A\mid C \cap \{200\})\cdot P(\{200\}\mid C)+\\ P(A\mid C \cap \{403\})\cdot P(\{403\}\mid C)=\\ P(A\mid \{200\})\cdot P(\{200\}\mid C)+ P(A\mid \{403\})\cdot P(\{403\}\mid C)=\\ 1\cdot P(\{200\}\mid C)+ 0\cdot P(\{403\}\mid C)=\frac{K}{N}$$