## Understanding how convolution of images work in cnn

i ‘d like to understand convolutional neural network. Consider the picture:

I don’t understand why the result of applying convolution to the 32by32by3 input image is not of size 32 by 32 by 3 by 12? From what I understand, we there are 12 filters and we apply each filter to each of the 3 channels of the image to get 3 new images for each filter.

Suppose the result of the first convolution is really 32 by 32 by 12, I don’t understand how you get them.

Also, what happen when we do a second convolution? Say we do a second full convolution with 5 filters, then the result of the second convolution is 32 by 32 by 3 by 12 by 5?

## Problem with understanding two sided Matching Algorithm: maximium cardinality

I am trying to understand the maximum cardinality problem in the context of stable matching algorithm. I am reading the following article at the link:

A Two-Sided Matching Decision Model Based on Uncertain Preference Sequences

The article says that:

In general, we can categorize two-sided matching problem into three typical kinds of models in terms of different decision objectives: stable matching, maximum cardinality matching, and maximum weight matching. In the first model, the objective is to seek a stable matching solution, and we count a solution as stable matching only when there does not exist any alternative pairing (𝐴, 𝐵) in which 𝐴 and 𝐵 are individually better off than they would be with the element currently matched. Gale and Shapley put forward an approach, also named Gale-Shapley algorithm, to get a stable matching solution in the perspective of mathematics and game theory, which symbolizes the beginning of two-sided matching research and enlightens the subsequent scholars to pay more attention to this topic. In the second model, the objective is to seek a solution in which the number of matching pairs is maximized.

I am able to understand stable matching. I can’t understand how the number of matching pair is maximized. This may occur because we have 2 sets. One of boys and other of girls. One element in one set has more than one matching in the other set. This might occur due to preference sequence. Am I right about maximum cardinality?

What I understand preference sequence as the order of preferences of elements of one set for the other. Due to maximum cardinality, it is possible that element Of one set has same preferences for multiple elements of the other set.

Am I right about preference sequences?

Zulfi.

## Understanding an example of an EXP-SPACE Problem

I am trying to understand the example given here of an EXP-SPACE time decision problem.

They write :

An example of an EXPSPACE-complete problem is the problem of recognizing whether two regular expressions represent different languages, where the expressions are limited to four operators: union, concatenation, the Kleene star (zero or more copies of an expression), and squaring (two copies of an expression)

Here is what I understand. Supposing I have some alphabet $$\Sigma = \{a,b,c…,z\}$$, then a regular expression is a pattern in order to specify the set of strings that belong to some language.

So for instance if I have two regular expressions, say

$$aa+a^{*}+bb^2$$ then any string that satisfies this expression is in $$L_1$$ (language 1),

$$abc$$ then any string that satisfies this expression is in $$L_2$$

Why does determining if these languages are the same in the worst case take exponential space. Further what is the size of the input ? I imagine it could be the sum of lengths of the two reg-expressions, but I am not sure.

Edit: If the Kleene star criterion is dropped, then I could see that we could simply create a set with all possible strings (the power set), and then compare the two sets.

## Understanding firewalls

I would like to understand how firewalls work in details, and understand the attack surface.

TCP and UDP

I understand that TCP and UDP are easy to filter. Programs on a computer need to ask the OS to open a port and will listen to these ports. Firewalls can simply look at all incoming packets, check the port number, and decide to allow it or not, based on the sending IP.

Are there attacks on other protocols ? What do firewalls do to protect from attacks from other protocols ?

Say there is a malware on a machine. Is the only possible way for the malware to communicate to the outside world is to open a TCP/UDP port? If we prevent a program from opening a TCP/UDP port, are we guaranteed that the program cannot communicate with the outside world?

## Why do I always have something missing in my understanding of topics which always lead me to solve problems incorrectly?

I am computer science masters student, i come from background of engineering and not cs, my problem is whenever i have a problem set, a programming task or an exam. i always try hard to understand the question and think for the right answers, but i usually either get stuck or have a wrong answer, and when i seek help i figure out i wasn’t completely understanding the topic of the question itself, missig some part of the information in or even having a wrong understanding to some parts.
So my question is, how i can approach a computer science topic “for e.g. operating systems” and have a good understanding with the right depth to have a better comprehension and to be able perform better at programming tasks and exams.

## Understanding INSERT … ON DUPLICATE KEY UPDATE deadlock scenario

I’m trying to understand a scenario where an `INSERT ... ON DUPLICATE KEY UPDATE` statement is causing deadlocks under high concurrency.

The two tables in question:

hosts:

``        "CREATE TABLE `hosts` (" +         "`id` int(10) unsigned NOT NULL AUTO_INCREMENT," +         "`osquery_host_id` varchar(255) NOT NULL," +         "`created_at` timestamp DEFAULT CURRENT_TIMESTAMP," +         "`updated_at` timestamp NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP," +         "`deleted_at` timestamp NULL DEFAULT NULL," +         "`deleted` tinyint(1) NOT NULL DEFAULT FALSE," +         "`detail_update_time` timestamp NULL DEFAULT NULL," +         "`node_key` varchar(255) DEFAULT NULL," +         "`host_name` varchar(255) NOT NULL DEFAULT ''," +         "`uuid` varchar(255) NOT NULL DEFAULT ''," +         "`platform` varchar(255) NOT NULL DEFAULT ''," +         "`osquery_version` varchar(255) NOT NULL DEFAULT ''," +         "`os_version` varchar(255) NOT NULL DEFAULT ''," +         "`build` varchar(255) NOT NULL DEFAULT ''," +         "`platform_like` varchar(255) NOT NULL DEFAULT ''," +         "`code_name` varchar(255) NOT NULL DEFAULT ''," +         "`uptime` bigint(20) NOT NULL DEFAULT 0," +         "`physical_memory` bigint(20) NOT NULL DEFAULT 0," +         "`cpu_type` varchar(255) NOT NULL DEFAULT ''," +         "`cpu_subtype` varchar(255) NOT NULL DEFAULT ''," +         "`cpu_brand` varchar(255) NOT NULL DEFAULT ''," +         "`cpu_physical_cores` int NOT NULL DEFAULT 0," +         "`cpu_logical_cores` int NOT NULL DEFAULT 0," +         "`hardware_vendor` varchar(255) NOT NULL DEFAULT ''," +         "`hardware_model` varchar(255) NOT NULL DEFAULT ''," +         "`hardware_version` varchar(255) NOT NULL DEFAULT ''," +         "`hardware_serial` varchar(255) NOT NULL DEFAULT ''," +         "`computer_name` varchar(255) NOT NULL DEFAULT ''," +         "`primary_ip_id` INT(10) UNSIGNED DEFAULT NULL, " +         "PRIMARY KEY (`id`)," +         "UNIQUE KEY `idx_host_unique_nodekey` (`node_key`)," +         "UNIQUE KEY `idx_osquery_host_id` (`osquery_host_id`)," +         "FULLTEXT KEY `hosts_search` (`host_name`)" +         ") ENGINE=InnoDB DEFAULT CHARSET=utf8;", ``

networks_interfaces:

``        "CREATE TABLE `network_interfaces` (" +         "`id` INT(10) UNSIGNED NOT NULL AUTO_INCREMENT," +         "`host_id` INT(10) UNSIGNED NOT NULL," +         "`mac` varchar(255) NOT NULL DEFAULT ''," +         "`ip_address` varchar(255) NOT NULL DEFAULT ''," +         "`broadcast` varchar(255) NOT NULL DEFAULT ''," +         "`ibytes` BIGINT NOT NULL DEFAULT 0," +         "`interface` VARCHAR(255) NOT NULL DEFAULT ''," +         "`ipackets` BIGINT NOT NULL DEFAULT 0," +         "`last_change` BIGINT NOT NULL DEFAULT 0," +         "`mask` varchar(255) NOT NULL DEFAULT ''," +         "`metric` INT NOT NULL DEFAULT 0," +         "`mtu` INT NOT NULL DEFAULT 0," +         "`obytes` BIGINT NOT NULL DEFAULT 0," +         "`ierrors` BIGINT NOT NULL DEFAULT 0," +         "`oerrors` BIGINT NOT NULL DEFAULT 0," +         "`opackets` BIGINT NOT NULL DEFAULT 0," +         "`point_to_point` varchar(255) NOT NULL DEFAULT ''," +         "`type` INT NOT NULL DEFAULT 0," +         "PRIMARY KEY (`id`), " +         "FOREIGN KEY `idx_network_interfaces_hosts_fk` (`host_id`) " +         "REFERENCES hosts(id) " +         "ON DELETE CASCADE, " +         "FULLTEXT KEY `ip_address_search` (`ip_address`)," +         "UNIQUE KEY `idx_network_interfaces_unique_ip_host_intf` (`ip_address`, `host_id`, `interface`)" +         ") ENGINE=InnoDB DEFAULT CHARSET=utf8;", ``

``------------------------ LATEST DETECTED DEADLOCK ------------------------ 2020-01-20 00:09:06 0x2b033abd2700 *** (1) TRANSACTION: TRANSACTION 78516922, ACTIVE 0 sec inserting mysql tables in use 1, locked 1 LOCK WAIT 5 lock struct(s), heap size 1136, 3 row lock(s), undo log entries 2 MySQL thread id 286926, OS thread handle 47297573750528, query id 1045761878 10.107.51.236 username update INSERT INTO network_interfaces (                         host_id,                         mac,                         ip_address,                         broadcast,                         ibytes,                         interface,                         ipackets,                         last_change,                         mask,                         metric,                         mtu,                         obytes,                         ierrors,                         oerrors,                         opackets,                         point_to_point,                         type                 ) VALUES (?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?)                 ON DUPLICATE KEY UPDATE                         id = LAST_INSERT_ID(id),                         mac = VALUES(mac),                         broadcast = VALUES(broadcast),                         ibytes = VALUES(ibytes),                         ipackets = VALUES(ipackets),                         last_change = VALUES(last_change),                         mask = VALUES(mask),                         metric = VALUES(metric),                         mtu = VALUES(mtu),                         obytes = VALUES(obytes),                         ierrors = VALUES(ierrors),                         oerrors = VALUES(oerrors),                         opackets = VALUES(opackets),                         point_to_point = VALUES(point_to_point),                         type = VALUES(type) *** (1) WAITING FOR THIS LOCK TO BE GRANTED: RECORD LOCKS space id 258 page no 2729 n bits 408 index FTS_DOC_ID_INDEX of table `kolide`.`network_interfaces` trx id 78516922 lock_mode Xinsert intention waiting Record lock, heap no 1 PHYSICAL RECORD: n_fields 1; compact format; info bits 0  0: len 8; hex 73757072656d756d; asc supremum;;  *** (2) TRANSACTION: TRANSACTION 78516915, ACTIVE 0 sec inserting mysql tables in use 1, locked 1 18 lock struct(s), heap size 1136, 33 row lock(s), undo log entries 12 MySQL thread id 281276, OS thread handle 47292870371072, query id 1045761879 10.107.78.241 username update INSERT INTO network_interfaces (                         host_id,                         mac,                         ip_address,                         broadcast,                         ibytes,                         interface,                         ipackets,                         last_change,                         mask,                         metric,                         mtu,                         obytes,                         ierrors,                         oerrors,                         opackets,                         point_to_point,                         type                 ) VALUES (?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?)                 ON DUPLICATE KEY UPDATE                         id = LAST_INSERT_ID(id),                         mac = VALUES(mac),                         broadcast = VALUES(broadcast),                         ibytes = VALUES(ibytes),                         ipackets = VALUES(ipackets),                         last_change = VALUES(last_change),                         mask = VALUES(mask),                         metric = VALUES(metric),                         mtu = VALUES(mtu),                         obytes = VALUES(obytes),                         ierrors = VALUES(ierrors),                         oerrors = VALUES(oerrors),                         opackets = VALUES(opackets),                         point_to_point = VALUES(point_to_point),                         type = VALUES(type) *** (2) HOLDS THE LOCK(S): RECORD LOCKS space id 258 page no 2729 n bits 408 index FTS_DOC_ID_INDEX of table `kolide`.`network_interfaces` trx id 78516915 lock_mode X Record lock, heap no 1 PHYSICAL RECORD: n_fields 1; compact format; info bits 0  0: len 8; hex 73757072656d756d; asc supremum;;  *** (2) WAITING FOR THIS LOCK TO BE GRANTED: RECORD LOCKS space id 258 page no 2729 n bits 408 index FTS_DOC_ID_INDEX of table `kolide`.`network_interfaces` trx id 78516915 lock_mode Xinsert intention waiting Record lock, heap no 1 PHYSICAL RECORD: n_fields 1; compact format; info bits 0  0: len 8; hex 73757072656d756d; asc supremum;;  *** WE ROLL BACK TRANSACTION (1) ``

The program starts a transaction, updates a host row, and uses that same transaction in a loop through all the host’s interfaces and issues a INSERT…ON DUPLICATE statement for each interface. As I understand it, because the transaction starts with a UPDATE (exclusive) lock on the host table, another transaction cannot be updating the same host. So I don’t think this is a scenario where two connections are trying to update the same set of host interfaces (this could easily result in a deadlock).

I think this might be due to different host updates competing over the AUTO_INCREMENT index of network_interfaces? I just don’t understand how, even after staring at the MySQL docs about locks. I understand that transaction 1 is waiting on an exclusive insert lock, transaction 2 has an exclusive lock and is also waiting on an exclusive insert lock. What I’m specifically not understanding is why TRANSACTION 2 has the exclusive lock `lock_mode X` to begin with.

## Understanding PoC of Windows CRYPT32.DLL vulnerability (CVE-2020-0601)

Kudelski Security have put up an interesting explanation of what the actual CVE-2020-0601 vulnerability is and also how it can potentially be exploited.

After reading this, I understand the basics of what was wrong in Windows implementation and how the PoC is supposed to work. The site also has a PoC setup where they generate a certificate which is signed using a rouge private key for a known CA (generated by manipulating the parameter `G` and known public key of the CA).

I downloaded the generated certificate and used OpenSSL to view its details

``\$   openssl x509 -inform der -in cert.crt -text Certificate:     Data:         Version: 3 (0x2)         Serial Number:             13:96:a7:9a:d9:71:d8:47:c3:fe:89:b2:b7:b6:57:40:28:9b:38:01     Signature Algorithm: ecdsa-with-SHA256         Issuer: C=CH, ST=Vaud, L=Lausanne, O=Kudelski Security PoC, OU=Research Team, CN=github.com         Validity             Not Before: Jan 16 00:03:54 2018 GMT             Not After : Oct 12 00:03:54 2020 GMT         Subject: C=CH, ST=Vaud, L=Lausanne, O=Kudelski Security, CN=github.com         Subject Public Key Info:             Public Key Algorithm: id-ecPublicKey                 Public-Key: (256 bit)                 pub:                      04:c6:54:aa:2c:11:14:b6:f5:c4:39:ea:80:95:7b:                     2c:b3:76:b0:90:f5:17:ec:7d:d6:48:6e:cd:63:58:                     cb:80:71:6b:bc:97:f5:26:4d:d0:7f:7b:cf:cb:05:                     0c:24:f3:29:55:5d:52:1d:74:2d:89:78:d9:9d:91:                     96:12:c5:cb:be                 ASN1 OID: prime256v1                 NIST CURVE: P-256         X509v3 extensions:             X509v3 Subject Alternative Name:                  DNS:*.kudelskisecurity.com, DNS:*.microsoft.com, DNS:*.google.com, DNS:*.wouaib.ch     Signature Algorithm: ecdsa-with-SHA256          30:65:02:31:00:f9:1b:4a:7b:d5:01:4d:f4:e3:42:5a:17:8c:          45:6f:39:ce:fd:ec:38:04:f0:78:93:84:5d:db:9c:db:41:07:          a3:97:cf:f3:6d:f6:8b:7b:38:5b:95:4e:a7:1f:9e:4a:0e:02:          30:08:29:0e:f2:d8:9c:e3:e4:15:67:b7:22:f6:de:80:56:18:          01:a0:d8:3e:28:ec:6c:bf:2a:28:a2:8f:fb:8a:b7:1e:c7:8f:          25:36:22:cd:86:1d:bf:6d:fa:fd:0f:a0:6f -----BEGIN CERTIFICATE----- MIICTzCCAdWgAwIBAgIUE5anmtlx2EfD/omyt7ZXQCibOAEwCgYIKoZIzj0EAwIw fDELMAkGA1UEBhMCQ0gxDTALBgNVBAgMBFZhdWQxETAPBgNVBAcMCExhdXNhbm5l MR4wHAYDVQQKDBVLdWRlbHNraSBTZWN1cml0eSBQb0MxFjAUBgNVBAsMDVJlc2Vh cmNoIFRlYW0xEzARBgNVBAMMCmdpdGh1Yi5jb20wHhcNMTgwMTE2MDAwMzU0WhcN MjAxMDEyMDAwMzU0WjBgMQswCQYDVQQGEwJDSDENMAsGA1UECAwEVmF1ZDERMA8G A1UEBwwITGF1c2FubmUxGjAYBgNVBAoMEUt1ZGVsc2tpIFNlY3VyaXR5MRMwEQYD VQQDDApnaXRodWIuY29tMFkwEwYHKoZIzj0CAQYIKoZIzj0DAQcDQgAExlSqLBEU tvXEOeqAlXsss3awkPUX7H3WSG7NY1jLgHFrvJf1Jk3Qf3vPywUMJPMpVV1SHXQt iXjZnZGWEsXLvqNRME8wTQYDVR0RBEYwRIIWKi5rdWRlbHNraXNlY3VyaXR5LmNv bYIPKi5taWNyb3NvZnQuY29tggwqLmdvb2dsZS5jb22CCyoud291YWliLmNoMAoG CCqGSM49BAMCA2gAMGUCMQD5G0p71QFN9ONCWheMRW85zv3sOATweJOEXduc20EH o5fP8232i3s4W5VOpx+eSg4CMAgpDvLYnOPkFWe3IvbegFYYAaDYPijsbL8qKKKP +4q3HsePJTYizYYdv236/Q+gbw== -----END CERTIFICATE----- ``

The certificate appears to be using a valid EC curve `P-256`. How can a person/process inspecting the certificate verify that it has indeed manipulated the EC parameters and is a fake?

## Quantum Computing: understanding the state vector

I have just started to learn QC. It is said that

The quantum state of N qubits can be expressed as a vector in a space of dimension 2^N

If there is 1 qubit then we have two possible state vectors |0> and |1> or (0,1) and (1,0) respectively. Getting to 2 qubits we have 4 possible state vectors `(1,0,0,0), (0,1,0,0), (0,0,1,0) and (0,0,0,1)`. Note that in each case, all entries are zero except 1. The point I am trying to get to is that:

1. 2^N seems like a big space but given a vector in this space – all components will be zero except 1. So there are only 2^N possible values the state vector can take. Is this not correct? If not, why?

1. Why don’t we say the space is N dimensional. A N-bit string has 2^N possible values.

## Textbook for understanding formal grammars

I am looking to understand the Chomsky Hierarchy. I’ve read some textbooks that touch on formal grammars (textbooks on computability, which relate automata to specific sets of formal grammars, notably context-free grammars and regular grammars), but not one that specifically deals with formal grammars as an object.

Is there a good textbook for this?